Desc.
求出满足如下条件的 $1$ 到 $n$ 的排列数量 (记排列为 $P = (p_1, \dots, p_n))$:
- $\forall i \in [1, n]$, 有 $\mid p_i-i\mid \geqslant X$.
$1 \leqslant n \leqslant 100$, $1 \leqslant X \leqslant 5$.
Sol.
$X$ 很小, 从这里入手. 注意到 $\geqslant X$ 的状态可能有很多, 但 $< X$ 的状态比较少, 因此计算补集. 考虑容斥, 设 $g_i$ 表示有 $i$ 个数不合法, 剩余数随意放置的方案数, $f_i$ 为恰好 $i$ 个不合法, 剩余数均合法的方案数. 有:
$$ g_i = \sum_{j=i}^n f_j \times \binom ji $$
由二项式反演:
$$ f_i = \sum_{j=i}^n (-1)^{j-i} \times \binom ji \times g_j $$
答案即为 $\displaystyle f_0 = \sum_{i=0}^n (-1)^i \times g_i$. 考虑怎么求 $g_i$. 设 $f_{i, j, s}$ 表示前 $i$ 个位置有 $j$ 个不合法, 其余位置不纳入考虑1, 且第 $i$ 个数的不合法区间当前的被占用情况为 $s$ 的方案数. 转移分当前数是否加入不合法讨论即可, 具体可以看代码.
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
const int MOD = 998244353;
using mint = modint<MOD>;
int n, X; cin >> n >> X;
const int LIM = 1<<(2*X-1), U = LIM-1;
vector f(n+1, vector(n+1, vector<mint>(LIM)));
f[0][0][0] = 1;
for (int i=0;i<n;++i) {
for (int j=0;j<=i;++j) {
for (int s=0;s<LIM;++s) {
f[i+1][j][s>>1] += f[i][j][s];
for (int p=0;p<2*X-1;++p)
if (!((s>>1)&(1<<p)) && i+2-X+p >= 1 && i+2-X+p <= n)
f[i+1][j+1][(s>>1)|(1<<p)] += f[i][j][s];
}
}
}
vector<mint> g(n+1), facs(n+1);
facs[0] = 1;
for (int i=1;i<=n;++i)
facs[i] = facs[i-1]*i;
for (int i=0;i<=n;++i)
g[i] = accumulate(allu(f[n][i]), mint(0));
mint ans = 0;
for (int i=0;i<=n;++i)
ans += (i&1?MOD-1:1)*g[i]*facs[n-i];
cout << ans << "\n";
}/ 来不及拒绝 /
/ 黑与白的纯洁 /
/ 视而不见 /
/ 假装不见 /
/ 凝望成永别 /
- 为什么其余位置不纳入考虑? 因为随意放置的方案数可以通过乘阶乘计算, 放入 DP 的计算里会很麻烦! ↩