这是NOIP良心模拟赛的第一题
求对于任意的 \(i\) 满足 \(|P_i - i| \not = k\) 的排列数。 \(n,k \le 10^5\)
首先 \(k=0\) 直接错排数。
\(k=1\) 考虑容斥。假设我们能算出来 \(g_i\) 表示钦定 \(i\) 个位置不合法的方案数，那么答案应该是
\[\sum_{i=0}^n(-1)^ig_i(n-i)!
\]
注意不是二项式反演，因为它并不需要反演，而是直接上容斥，我们可以轻松地用 \(g\) 来表示答案。
现在我们需要求出 \(g_i\)，即钦定 \(i\) 个位置不合法的方案数。
虽然我们是在钦定“不合法位置”，但是那只是不符合 \(|P_i - i| \not= k\)，还需要符合排列的性质，即不能让两个位置是同一个数。我们发现这种限制关系可以被划分成 \(n/k\) 条链，每条链是由若干相距 \(k\) 的元素组成的。链与链之间独立，可以直接背包。故现只考虑一条链上选 \(i\) 个的方案数。
建立图论模型：将其看做二分图，发现左右部的出边是互不影响的，于是可以拆成两条链。对于一条链来说，我们对其的要求就仅有不能选择相邻的两个元素。此模型详见我的博客，答案是 \({l - i + 1 \choose i}\)
这样我们就得到了一些背包，我们的任务是把他们合并起来。而这个可以用 NTT 优化到 \(n^2logn\)。并且发现这些背包只有两种，于是可以多项式快速幂搞。复杂度 \(O(nlogn)\)。又发现背包元素只有 \(n/k\)，于是我们可以直接取够 \(n\) 个样本然后直接 DFT 后快速幂即可。复杂度 \(O(nlogP)\)
Code:
ll f1[N], f2[N];
ll A[N], B[N];
int r[N];
int limi = 1, L;
inline void init() {
jie[0] = jieni[0] = 1;
for (register int i = 1; i <= limi; ++i) jie[i] = jie[i - 1] * i % P;
jieni[limi] = quickpow(jie[limi], P - 2);
for (register int i = limi - 1; i; --i) jieni[i] = jieni[i + 1] * (i + 1) % P;
}
int ct;
inline void ntt(ll *a, int type)
ll tmp[N];
inline void Mul(ll *a, ll *b)
inline void Pow(ll *a, int k) {
ntt(a, 1);
for (register int i = 0; i < limi; ++i) a[i] = quickpow(a[i], k);
ntt(a, -1);
for (register int i = n + 1; i < limi; ++i) a[i] = 0;
}
int main() {
read(n), read(k);
while (limi <= n + n) limi <<= 1, ++L;
for (register int i = 0; i < limi; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
init();
int nwn = n / k;
for (register int i = 0; i <= n; ++i) f1[i] = get_c(nwn - i + 1, i);
--nwn;
for (register int i = 0; i <= n; ++i) f2[i] = get_c(nwn - i + 1, i);
Pow(f1, (n % k) * 2); Pow(f2, (k - n % k) * 2);
Mul(f1, f2);
ll ans = 0;
for (register int i = 0; i <= n; ++i)
if (i & 1) ans = (ans - f1[i] * jie[n - i]) % P;
else ans = (ans + f1[i] * jie[n - i]) % P;
printf("%lld\n", (ans % P + P) % P);
return 0;
}