前言
题目链接：Codeforces；洛谷。
题意简述
你有一个长度为 \(n\) 的序列 \(p\) 满足 \(p_i=i\)，你可以进行 \(x\) 次操作，每次操作找到两个不同的 \(i,j\) 并且交换 \(p_i,p_j\)，问最终有几个可能的序列。分别求出 \(x = 1, \ldots, k\) 时的答案。
\(1 \le n \le 10^9\)，\(1\le k \le 200\)。
题目分析
先考虑暴力 DP。显然原问题等价于求有多少排列经过 \(x\) 次交换后得到 \(p_i = i\)。设 \(f_i(x)\) 表示有多少长度为 \(x\) 的排列，至少经过 \(i\) 次操作可以得到原序列。边界 \(f_0(x) = 1\)。考虑转移。对于 \(f_i(x)\) 考虑 \(p_x\) 的值。若 \(p_x = x\)，有 \(f_i(x) = f_i(x - 1)\)；否则需要进行一次交换 \(f_i(x) = f_{i - 1}(x - 1)\)。综合得到 \(f_i(x) = f_i(x - 1) + f_{i - 1}(x - 1)\)。由于我们总是能浪费偶数次操作，所以对于一个 \(x\)，答案为 \(\sum f_{x - 2t}(n)\)。
这么做时间复杂度是 \(\Theta(nk)\) 的。
显然瓶颈在于 \(n\)，考虑优化掉它。发现进行 \(x\) 次操作，最多只有 \(2x\) 个关键点发生变化，不妨从这里入手。
不妨枚举有 \(i\) 个位置发生了变化，类似浪费 \(2t\) 次操作，对答案的贡献为 \(\binom{n}{i} \sum g_{x - 2t}(i)\)，其中 \(g_i(x)\) 表示有多少长度为 \(x\) 的序列，每一个位置都发生了变化，至少经过 \(i\) 次操作变回原序列。
显然 \(g\) 不等价于 \(f\)，因为 \(f\) 计算的时候可能存在 \(p_i = i\)。不妨找找二者关系。我们原本可以用 \(f\) 表示出答案，现在答案和 \(g\) 有关，说明 \(f\) 也能够由 \(g\) 表示出。发现如果我们类比统计答案，钦定只有某些位置发生变化，有：
\[f(x) = \sum _ {i = 0} ^ x \binom{x}{i} g(i) \]这很二项式反演，不会的可以看看我的《学习笔记》。
根据经典定理，我们得到：
\[g(x) = \sum _ {i = 0} ^ x (-1) ^ {x - i} \binom{x}{i} f(i) \]于是问题迎刃而解。时间复杂度 \(\Theta(k^3)\)。
代码
#include <cstdio>
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
inline int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
inline int sub(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
inline int mul(int a, int b) {
return 1ll * a * b % mod;
}
int n, k;
int f[420][420], g[420][420];
int frac[420], Inv[420], ifrac[420], tfrac[420];
void init(int n = 400) {
frac[0] = ifrac[0] = tfrac[0] = 1;
for (int i = 1; i <= n; ++i) {
frac[i] = mul(frac[i - 1], i);
Inv[i] = i == 1 ? 1 : sub(0, mul(mod / i, Inv[mod % i]));
ifrac[i] = mul(ifrac[i - 1], Inv[i]);
tfrac[i] = mul(tfrac[i - 1], ::n - i + 1);
}
}
inline int C(int m) { // C(n, m) = n * ... * (n - m + 1) / m!
return mul(tfrac[m], ifrac[m]);
}
inline int C(int n, int m) {
return mul(frac[n], mul(ifrac[n - m], ifrac[m]));
}
signed main() {
scanf("%d%d", &n, &k), init(), f[0][0] = 1;
for (int i = 1; i <= min(n, k << 1); ++i) {
f[i][0] = 1;
for (int j = 1; j <= k; ++j) {
f[i][j] = add(f[i - 1][j], mul(i - 1, f[i - 1][j - 1]));
}
}
for (int i = 0; i <= min(n, k << 1); ++i)
for (int j = 0; j <= k; ++j)
for (int x = 0; x <= i; ++x) {
if ((i - x) & 1)
g[i][j] = sub(g[i][j], mul(C(i, x), f[x][j]));
else
g[i][j] = add(g[i][j], mul(C(i, x), f[x][j]));
}
for (int i = 1; i <= k; ++i) {
int res = 0;
for (int j = min(i << 1, n); j >= 0; --j) {
if (i >= 2) g[j][i] = add(g[j][i], g[j][i - 2]);
res = add(res, mul(g[j][i], C(j)));
}
printf("%d ", res);
}
return 0;
}