自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:36，当前版本为作者最后更新于2022-09-01 11:04:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

D1T2. P8497 [NOI2022] 移除石子

这道题目比较抽象，比较人类智慧。

对于合法序列计数题，首先必须会判定合法序列，即考虑 $l_i = r_i$ 的部分分。

从最基本的 $\boldsymbol{k = 0}$ 入手 找一些性质：

• 区间长度要求 $\geq 3$ 等价于区间长度为 $3, 4, 5$，经典套路。

• 不会进行相同的操作二，可用若干操作一代替。

设计类插头 DP $f_{i, j, k, l}$ 表示当前已经决策好从 $< i$ 的位置开始的操作二，有 $j$ 个可以延伸到 $i$，$k$ 个必须延伸到 $i$，$l$ 个必须延伸到 $i + 1$，是否可行。转移即枚举从 $i$ 开始的操作二个数 $m$，可知不超过 $3$，再枚举 $j$ 个可以扩展到 $i$ 的操作二中真实扩展的数量 $p$，若 $a_i - k - l - m - p$ 小于 $0$ 或等于 $1$ 则非法，否则令 $f_{i + 1, p + k, l, m} = 1$。检查是否存在 $f_{n + 1, *, 0, 0} = 1$ 即可。

根据分析，$j$ 这一维大小只需设成 $3$，$k \leq 3$，$l\leq 3$ 即可覆盖至少一个可行解：

• 到 $i - 1$ 长度已经等于 $3$ 且还要继续延伸到 $\geq i$ 的位置的区间只可能是 $[i - 3, i]$，$[i - 3, i + 1]$ 和 $[i - 4, i]$，因此 $j\leq 3$。
• 从每个位置开始的操作二数量 $\leq 3$，因此 $k, l\leq 3$。

上述做法已经可以通过该档部分分。

进一步地，我们发现 $j, k$ 这两维可以融合在一起。具体地，我们在决策 $i$ 的时候，与其分别记录可以和必须延伸到 $i + 1$ 的数量，不妨直接钦定有多少个真实扩展到 $i + 1$，因为在 $i + 1$ 处这些操作二长度均 $\geq 3$，就等价了。

因此，设 $f_{i, j, k}$ 表示当前决策好从 $< i$ 的位置开始的操作二，有 $j$ 个钦定被延伸到 $i$，且有 $k$ 个必须延伸到 $i + 1$。转移时枚举从 $i$ 开始的操作二个数 $l$，若 $a_i - j - k - l$ 小于 $0$ 或等于 $1$ 则非法，否则钦定被延伸到 $i + 1$ 的操作二数量 $p\in [k, k + j]$，令 $f_{i + 1, p, l} = 1$ 即可。检查是否存在 $f_{n + 1, 0, 0}$ 即可。

类似分析，可知 $j\leq 6$，$k\leq 3$。

进一步挖掘性质，我们发现

• 若从一个位置开始同时有长度为 $4, 5$ 的操作二，可以简化成一次操作一和从下一个位置开始长度为 $3, 4$ 的操作二。

因此 $j\leq 4$，$k\leq 2$ 仍合法。

进一步地，我们枚举跨过 $i - 1$ 延伸到 $i$ 且在 $i$ 处长度 $\geq 3$ 的操作二的所有可能情况，发现所有操作二个数 $\geq 3$ 的情况都可以被简化成若干次操作一和不超过 $2$ 次操作二，因此 $j\leq 2$ 仍合法。考场上可以不断缩小 DP 某一维度并对拍从而简化状态，然后你就 win 了。

时间复杂度 $\mathcal{O}(n)$。代码。

考虑 $\boldsymbol{k > 0}$。这个「恰好」就很烦人，尝试把它弱化成「至多」，并消除弱化带来的影响。换言之，我们需要找到所有状态，使得添加小于 $k$ 个石子有解，但添加 $k$ 个石子后没有解。

• 若 $k = 0$ 显然不影响。

• 若 $k = 1$，考虑不添加任何石子的有解局面最终方案：

  • 若存在至少一次操作一则必然有解，直接将石子放在操作一位置上即可。
  • 若存在长度 $> 3$ 的操作二则必然有解，将石子放在操作二左端变成一次操作一和一次操作二即可。
  • 若存在长度 $= 3$ 的操作二且 $n > 3$ 则必然有解，将石子放在操作二两侧某空位上（$n > 3$ 故存在），变成一次长度 $= 4$ 的操作二即可。

  综合上述分析，可知非法当且仅当 $n = 3$ 且 $a_1 = a_2 = a_3 = 1$，或 $a_i = 0$。

• 若 $k = 2$：

  • 若 $k = 0$ 有解，将两颗石子放在任意位置用一次操作一处理，得出 $k = 2$ 有解。
  • 若 $k = 1$ 有解，考察所有 添加一颗石子，有解变无解 的局面，即 $n = 3$ 且 $a_1 = a_2 = a_3 = 1$，或 $a_i = 0$。去掉一颗石子，要么没有石子可以去掉，即这种情况不可能发生，要么总可以重新添加两颗石子使得有解。

  综合上述分析，若局面添加小于两颗石子有解，则添加两颗石子有解。

• 同理可证对于任意 $k > 2$，若局面添加小于 $k$ 颗石子有解，则添加 $k$ 颗石子有解。

特判掉 $\boldsymbol{k = 1}$ 的两种情况，若局面添加小于 $k$ 颗石子有解，则添加 $k$ 颗石子有解。

综上，设 $g_{i, j, k}$ 表示为使得 $f_{i, j, k} = 1$ 至少添加的石子数。转移类似 $f$ 枚举 $l$，设 $v = a_i - j - k - l$，设 $need$ 表示使得 $i$ 合法至少添加的石子数，则当 $v < 0$ 时，$need = -v$，否则若 $v = 1$ 则 $need = 1$，否则 $need = 0$。类似 $f$ 枚举 $p$，则 $g_{i + 1, p, l}$ 与 $g_{i, j, k} + need$ 取最小值。检查是否存在 $g_{n + 1, 0, 0} \leq k$ 即可。

时间复杂度 $\mathcal{O}(n)$，代码。

从 $k = 0$ 出发还有一个方向，就是 对 $\boldsymbol{k = 0}$ 计数。

由于之前我们已经对状态进行了充足的简化，$f_i$ 仅有 $9$ 个状态，因此考虑 DP 套 DP，设 $f_{i, S}$ 表示这九种状态的取值状态为 $S$ 的方案数。显然对于较大的 $a_i$，它们等价。具体地，由于 $j, k, l\leq 2$，所以 $\geq 8$ 的 $a_i$ 是等价的。在一开始预处理出 $tr(S, v)$ 表示从九种状态的取值状态为 $S$ 的 $f_i$ 开始，令 $a_i = v$，转移到的 $f_{i + 1}$ 的九种状态的取值状态。转移时只需枚举 $S$ 和 $a_i$，若 $a_i\leq 7$ 且 $l_i\leq a_i\leq r_i$ 则 $f_{i + 1, tr(S, a_i)}$ 受到 $f_{i, S}$ 的贡献，若 $a_i = 8$ 则 $f_{i + 1, tr(S, a_i)}$ 受到 $f_{i, S} \times |\mathbb{Z} \cap [l_i, r_i] \cap [8, +\infty)|$ 的贡献。

通过对拍我们发现 $\geq 6$ 的 $a_i$ 就是等价的，感性理解是当 $j = k = 2$ 时根本不用从 $i$ 开始新开两个操作 $2$，$j + k + l = 5$ 的情况类似。这个也挺玄学的。

对于最终态 $f_{n + 1, S}$，若 $S$ 对应 $j = k = 0$ 的位取值为 $1$，则 $f_{n + 1, S}$ 贡献至答案。时间复杂度 $\mathcal{O}(nS)$，代码。

将对 $k = 0$ 计数和对 $k > 0$ 判定结合起来，因为 $g_{i, j, k}$ 有 $0\sim 101$ 这 $102$ 种取值，所以乍一看状态数是 $102 ^ 9$ 级别。但我们的感知告诉我们有很多状态都是达不到的，因为 $g_{i, j, k}$ 在 $j, k$ 取不同的值时，相差一定不会很大。写个爆搜发现只有 $S = 8765$ 种状态，于是你就过了这道题目，赢麻了。

时间复杂度 $\mathcal{O}(nS)$。

总结：D1T2 和 D2T2 都是从简化问题入手，通过结合两个问题维度上的扩展得到正解，做这两道题让我受益匪浅。这让我想到了平行四边形，给它加上对角线相等的条件就成了矩形，给它加上邻边相等的条件就成了菱形，将两者结合在一起就成了正方形。有的时候从平行四边形到正方形是困难的，但从平行四边形到矩形和菱形是自然的，而它们的结合也是自然的。这给出了我们思考问题的一条有效的道路，同时也说明了为什么从部分分开始思考，一步一步打暴力是优秀的。我希望大家都能体会到这一点。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
inline int read() {
  int x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 1e3 + 5;
constexpr int S = 8765;
constexpr int mod = 1e9 + 7;
void cmin(int &x, int y) {x = x < y ? x : y;}
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
int n, k, l[N], r[N], node, f[S], g[S], tr[S][7];
map<vector<int>, int> mp;
int dfs(vector<int> cur) {
  if(mp.find(cur) != mp.end()) return mp[cur];
  int ind = mp[cur] = node++;
  for(int a = 0; a < 7; a++) {
    vector<int> suc(9, 101);
    for(int j = 0; j < 3; j++)
      for(int k = 0; k < 3; k++) {
        int v = cur[j * 3 + k];
        if(v == 101) continue;
        for(int st = 0; st < 3; st++) {
          int val = a - j - k - st;
          int need = val < 0 ? -val : val == 1 ? 1 : 0;
          for(int nj = k; nj <= min(2, j + k); nj++) cmin(suc[nj * 3 + st], v + need);
        }
      }
    tr[ind][a] = dfs(suc);
  }
  return ind;
}
void solve() {
  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
  memset(f, 0, sizeof(f)), f[0] = 1;
  for(int i = 1; i <= n; i++) {
    memset(g, 0, sizeof(g));
    for(int j = 0; j < S; j++) {
      if(!f[j]) continue;
      for(int a = 0; a < 7; a++) {
        int coef = 0;
        if(a < 6) coef = l[i] <= a && a <= r[i];
        else if(r[i] >= 6) coef = r[i] - max(6, l[i]) + 1;
        if(coef == 1) add(g[tr[j][a]], f[j]);
        else if(coef > 0) add(g[tr[j][a]], 1ll * f[j] * coef % mod);
      }
    }
    swap(f, g);
  }
  int ans = 0;
  for(auto it : mp) if(it.first[0] <= k) add(ans, f[it.second]);
  if(k == 1) {
    bool all0 = 1;
    for(int i = 1; i <= n; i++) all0 &= !l[i];
    if(all0) ans--;
    if(n == 3 && l[1] <= 1 && r[1] >= 1 && l[2] <= 1 && r[2] >= 1 && l[3] <= 1 && r[3] >= 1) ans--;
  }
  cout << (ans % mod + mod) % mod << "\n";
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("b.in", "r", stdin);
    FILE* OUT = freopen("b.out", "w", stdout);
  #endif
  vector<int> I(9, 101);
  I[0] = 0, dfs(I);
  cerr << node << endl;
  int T;
  cin >> T;
  while(T--) solve();
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/8/31
author: Alex_Wei
start coding at 17:50
finish debugging at 21:17
*/