Baby Ehab Plays with Permutations | Codeforces 1516E

题目链接

给定 \(n,k\)，对于每个 \(i \in [1,k]\)，你需要求出有多少个长度为 \(n\) 的排列能通过恰好 \(i\) 次交换操作变成 \(\{1,2,\cdots,n\}\)。

答案对 \(10^9+7\) 取模。

\(n \le 10^9,k \le 200\)

先考虑这样一个问题：给定一个排列 \(P\)，最少交换几次才能变成 \(\{1,2,\cdots,n\}\)。

把排列 \(P\) 理解成一个置换，并分解成循环，不难发现 \(i\) 个元素的循环需要交换 \(i-1\) 次。

这样，如果 \(P\) 的循环节为 \(x\)，则总的交换次数为 \(n-x\)。

涉及到点数和循环数不难想到第一类斯特林数。

\(i\) 的答案即 \({n \brack n-i}+{n \brack n-i+2}+{n \brack n-i+4} + \cdots\)。

问题是 \(n\) 太大了，不能递推求出第一类斯特林数。

由于 \(i\) 次交换最多影响 \(2i\) 个元素，一个合法的排列 \(P\) 至多有 \(2i\) 个位置 \(j\) 满足 \(j \ne P_j\)。

可以枚举有多少个 \(j\) 满足 \(j \ne P_j\)，如果有 \(x\) 个，对答案的贡献为 \(\binom nxf_{x,x-i}\)。

其中 \(f_{i,j}\) 表示有多少个长度为 \(i\) 的错排循环节为 \(j\)，它可以通过第一类斯特林数容斥得到： \[ f_{i,j}={i \brack j}-\sum_{k=1}^j\binom ikf_{i-k,j-k} \] 复杂度 \(O(k^3)\)。

代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define pb push_back

using namespace std;

typedef long long ll;
const int N = 205;
const ll P = 1e9 + 7;

int n, K, C[N * 2][N * 2];
ll f[N * 2][N], as[N];

ll Pow(ll a, int n, ll r = 1) {
    for(; n; n /= 2, a = a * a % P)
    if(n & 1) r = r * a % P;
    return r;
}
ll calc(int x) {
    ll a = 1, b = 1;
    while(x) b = b * x-- % P, a = a * (n - x) % P;
    return a * Pow(b, P - 2) % P;
}
int main() {
    cin >> n >> K;
    f[0][0] = 1;
    rep(i, 1, K * 2) rep(j, 1, K)
        f[i][j] = (f[i - 1][j - 1] + (i - 1) * f[i - 1][j]) % P;
    rep(i, 0, K * 2) {
        C[i][0] = 1;
        rep(j, 1, i) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
    rep(i, 1, K * 2) rep(j, 1, i) rep(k, 1, j)
        (f[i][j] -= C[i][k] * f[i - k][j - k]) %= P;
    rep(i, 0, K) {
        rep(j, i, i * 2) (as[i] += f[j][j - i] * calc(j)) %= P;
        if(i >= 2) (as[i] += as[i - 2]) %= P;
        if(i) printf("%lld ", (as[i] + P) % P);
    }
    return 0;
}