P8497 [NOI2022] 移除石子

Alex_Wei · 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
*/