CF2119D Token Removing 题解

· · 题解

出题人题解。附上题目中歌曲的 B 站链接：r-906 & Hatsune Miku - あなたしか見えないの。

抱歉，我错误地判断了问题 D 的难度。

提示

计算单个有效序列的权重很困难。试试其他方法？

题解

考虑首先确定最后有哪些 token 被移除了。然后我们需要对于每个将要被移除的 token，假设这个 token 位于 p_i，我们需要找一个包含 p_i 的区间 [l_i, r_i]，且满足所有的 r_i 互不相同。

我们使序列 a 满足所有的 a_{r_i} = l_i，其他位置为 0，并且第 r_i 次操作正好移除 p_i，就得到了一个区间组与合法操作方案的双射，那么我们只需要对于所有 2^n 个最后被移除的 token 位置集合算出找区间的方案并求和即可。

假设这些 token 的位置分别为 n \ge p_0 > p_1 > \dots > p_{k - 1} \ge 1，那么找区间的方案显然就是 \prod_{i = 0}^{k - 1} p_i(n - p_i + 1 - i)。我们设计如下 DP：设 f_{i, j} 表示 p_{k - 1} \ge n - i + 1 且 k = i - j 时，\prod_{i = 0}^{k - 1} p_i(n - p_i + 1 - i) 的和。考虑 p_{k - 1} 是否等于 n - i + 1，我们得到如下转移：

f_{i, j} = f_{i - 1, j - 1} + (n - i + 1)(j + 1) f_{i - 1, j}

最后答案即为 \sum_{j = 0}^n f_{n, j}。总时间复杂度为 \mathcal{O}(\sum n^2)，可以通过。

代码实现

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 5005;
int t, n, mod, f[N][N], ans;
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
int main(){scanf("%d", &t);
    while (t --){scanf("%d%d", &n, &mod), f[0][0] = 1, ans = 0;
        for (int i = 1;i <= n;i ++) for (int j = 0;j <= i;j ++) f[i][j] = 0;
        for (int i = 1;i <= n;i ++)
        for (int j = 0, now;j < i;j ++)
        if (now = f[i - 1][j]) add(f[i][j + 1], now),
        f[i][j] = (f[i][j] + (n - i + 1ll) * (j + 1) * now) % mod;
        for (int j = 0;j <= n;j ++) add(ans, f[n][j]);printf("%d\n", ans);
    }
}