排列

发表于 2021-10-21

【雅礼2019.10.17amT1】排列

思路

问题其实是问恰好有 $0$ 个 $i$ 满足 $|P_i - i| = k$ 的方案数.

考虑二项式反演，先求出钦定 $k$ 个 $i$ 满足 $|P_i - i| = k$ 的方案数.

可以看作一张二分图，上面的点表示 $P_i$ ，下面的点表示 $i$ , 如果 $|P_i - i| = k$ 就连边。

钦定 $k$ 个 $i$ 满足 $|P_i - i| = k$ 的方案数.就是选出 $k$ 条边的方案数乘 $(n - k)!$

发现这个二分图可以看成一些独立的链，而且这些链只有两种长度。

考虑对于一条链求方案数。

设 $f[i][j][0/1]$ 表示选到了第 $i$ 个点，已经选了 $j$ 条边，这个点是否选的方案数.

有

f[i][j][0] = f[i - 1][j][1] + f[i - 1][j][0]\\ f[i][j][1] = f[i - 1][j - 1][0]\\

发现可以直接用 $f[i - 1][j - 1][0]$ 表示 $f[i][j][1]$

于是设 $f[i][j]$ 表示选到了第 $i$ 个点，已经选了 $j$ 条边的方案数.

$f[i][j] = f[i - 1][j] + f[i - 2][j - 1]$

发现和二项式系数递推式很像，只是每选一个，可以用来选的元素的个数会减少 $2$ , 所有其实就是 $C(i - j, j)$

会了链的做法，然后因为这些链是独立的，所有可以很容易的拼成二分图的做法.

设 $g[n]$ 表示在二分图上选出 $n$ 条边的方案数. $len_i$ 表示第 $i$ 条链的点的个数, 如果一共可以分成 $k$ 条链，那么显然有

$g[n] = \sum_{a_1+a_2+...+a_k=n}\prod_{i=1}^{k}f[len_i][a_i]$

考虑用生成函数，用 $F(len)$ 表示 $f[len]$ 的 $OGF$ 。
设两种链长分别为 $len$ 和 $len+1$ ，出现次数为 $cnt1$ , $cnt2$ .

那么有 $g[n] = [x^n]F(len)^{cnt1}*F(len + 1)^{cnt2}$ ，可以 $FFT$ 求.

然后根据二项式反演有 $ans = \sum_{i=0}^{n}\tbinom{i}{0}g[i](n - i)!(-1)^{i-0} = \sum_{i=0}^{n}g[i](n - i)!(-1)^{i}$ .

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long

using namespace std;

const int N = 5e5 + 10;
const int mod = 998244353, G = 3;
int n, k;
int f[N];
int tr[N];
int invG;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

int sub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

void dft(int *f, int n, int op) {
    for (int i = 0; i < n; ++i) {
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
    }
    for (int i = 0; i < n; ++i) {
        if (i < tr[i]) swap(f[i], f[tr[i]]);
    }
    for (int p = 2; p <= n; p <<= 1) {
        int len = p / 2;
        int tG = qpow(op ? G : invG, (mod - 1) / p);
        for (int l = 0; l < n; l += p) {
            int buf = 1;
            for (int k = l; k < l + len; ++k) {
                int tmp = buf * f[k + len] % mod;
                f[k + len] = sub(f[k], tmp);
                f[k] = add(f[k], tmp);
                buf = buf * tG % mod;
            }
        }
    }
    int invn = qpow(n, mod - 2);
    if (!op) {
        for (int i = 0; i < n; ++i) f[i] = f[i] * invn % mod;
    }
}

int res[N];
int fac[N], ifac[N], inv[N];
int a[N], b[N];
int cnt1, cnt2;

int C(int n, int m) {
    if (n < m) return 0;
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int g[N];

signed main() {
    scanf("%lld%lld", &n, &k);
    inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    for (int i = 0; i <= (n - 1) / k; ++i) {
        a[i] = C((n - 1) / k + 1 - i, i);
    }
    for (int i = 0; i < (n - 1) / k; ++i) {
        b[i] = C((n - 1) / k - i, i);
    }
    cnt1 = (n - 1) % k + 1;
    cnt2 = k - cnt1;
    invG = qpow(G, mod - 2);
    int m = n;
    for (n = 1; n <= m + 1; n <<= 1);
    dft(a, n, 1), dft(b, n, 1);
    for (int i = 0; i <= n; ++i) {
        g[i] = qpow(a[i], cnt1 * 2) * qpow(b[i], cnt2 * 2) % mod;
    }
    dft(b, n, 0);
    dft(g, n, 0);
    int ans = 0;
    for (int i = 0; i <= m; ++i) {
        if (i & 1) ans = sub(ans, g[i] * fac[m - i]) % mod;
        else ans = add(ans, g[i] * fac[m - i]) % mod;
    }
    printf("%lld", ans);
    return 0;
}

总结

考虑 $dp$ 式的组合意义，有助于转化成封闭形式。
通过对匹配问题，建立二分图的图论模型，可以发现一些有价值的性质，在这到题中体现为发现二分图其实是一些独立的链。且只有两种链长。
$dp$ 化简有一种常见方式，就是把两种状态转移的方程式进行代入消元。
越简单的递推式越容易转化成封闭形式。

【雅礼2019.10.17amT1】排列

标签

思路

Code

总结