CF285E Positions in Permutations

前言

要不是吴老师让我讲组合,我估计现在还不会这题呢…

题意

排列P(p_1,p_2,…,p_n)被认为是好的,当且仅当恰好有k个位置满足|p_i-i|=1,给定N,K(1\le n\le 1000, 0\le k\le n),求满足条件的好排列个数,对10^9+7取模。

分析

我们发现直接算不是很方便,考虑用容斥。
g(k)表示恰好k个位置满足的方案数,f(k)表示至少k个位置满足的方案数。我们先来看如何求f.
考虑条件|p_i-i|=1,对于位置集合X=\lbrace 1,2,…,n\rbrace,数集Y=\lbrace 1,2,…,n\rbrace,这个问题就转化为了X和Y构成的二分图的一个匹配问题,X中的元素x_i与Y中的元素x_i-1x_i+1有边(1,n例外)。介于图较为复杂,我们用动态规划计数。设DP[i][j]表示我们匹配到X,Y的第i个位置,匹配的j对点的方案数(我们只考虑与当前点与之前的点匹配),发现这样的状态并不够。那么我们再加两维,表示X中的第i个点和Y中的第i个点的匹配状态,这样就可以进行转移了。那么f(k)=\sum DP[N][k][0/1][0/1]\ast (N-k)!.
接下来看一下f和g的关系:f(n)=\sum\limits_{i\ge n}{i\choose n}g(i).这里我们知道了f,就可以用反演来推出g.推理如下:

首先g(n)可以被这样表示:
g(n)=\sum\limits_{k\ge n} [k-n=0]{k\choose n}g(k)

\sum\limits_{k=0}^n(-1)^k{n\choose k}=[n=0]
带入得
g(n)=\sum\limits_{k\ge n}\sum\limits_{i=0}^{k-n}(-1)^i{k-n\choose i}{k\choose n}g(k)=\sum\limits_{k\ge n}\sum\limits_{i=0}^{k-n}(-1)^i{i+n\choose n}{k\choose i+n}g(k)
其等价于
g(n)=\sum\limits_{i\ge n}\sum\limits_{k\ge i}(-1)^{i-n}{i\choose n}{k\choose i}g(k)=\sum\limits_{i\ge n}(-1)^{i-n}{i\choose n}\sum\limits_{k\ge i}{k\choose i}g(k)
将后面的和式替换为f,即:
g(n)=\sum\limits_{i\ge n}(-1)^{i-n}{i\choose n}f(i)

这样这题就做完了!

参考代码

typedef long long LL;
const int MAXN = 1010;
const int MOD = 1e9 + 7;

int DP[MAXN][MAXN][2][2], N, K, fac[MAXN], inv[MAXN];

inline LL C(int n, int r) { return (LL)fac[n] * inv[r] % MOD * inv[n - r] % MOD; }
void add(int & x, int d) { (x += d) %= MOD; }
void init();

int main() {
    scanf("%d%d", &N, &K);
    init();
    DP[0][0][0][0] = 1;
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= N; j++) {
            add(DP[i][j][0][0], DP[i - 1][j][0][0]);
            add(DP[i][j][0][0], DP[i - 1][j][0][1]);
            add(DP[i][j][0][0], DP[i - 1][j][1][0]);
            add(DP[i][j][0][0], DP[i - 1][j][1][1]);
            if (j >= 1 && i > 1) {
                add(DP[i][j][0][1], DP[i - 1][j - 1][0][0]), add(DP[i][j][0][1], DP[i - 1][j - 1][0][1]);
                add(DP[i][j][1][0], DP[i - 1][j - 1][0][0]), add(DP[i][j][1][0], DP[i - 1][j - 1][1][0]);
            }
            if (j >= 2 && i > 1) add(DP[i][j][1][1], DP[i - 1][j - 2][0][0]);
        }
    int ans = 0;
    for (int i = K; i <= N; i++)
        add(ans, (i - K & 1 ? -1LL : 1LL) * C(i, K) * fac[N - i] % MOD * (((LL)DP[N][i][0][0] + DP[N][i][0][1] + DP[N][i][1][0] + DP[N][i][1][1]) % MOD) % MOD);
    ans = (ans + MOD) % MOD;
    printf("%d\n", ans);
    return 0;
}

LL fast_pow(LL bs, int ex) {
    LL res = 1;
    for (; ex; (bs *= bs) %= MOD, ex >>= 1) if (ex & 1) (res *= bs) %= MOD;
    return res;
}

void init() {
    fac[0] = 1;
    for (LL i = 1; i <= N; i++) fac[i] = i * fac[i - 1] % MOD;
    inv[N] = fast_pow(fac[N], MOD - 2);
    for (LL i = N - 1; i >= 0; i--) inv[i] = (i + 1) * inv[i + 1] % MOD;
}

总结

思考这题的时候没有马上反应过来是容斥。做容斥的时候,DP加状态不够果断,推式子也推了好久,这反映出来对反演还不够熟练,并且和式的转化也未到火候。

About The Author

1 thought on “CF285E Positions in Permutations

发表评论

电子邮件地址不会被公开。 必填项已用*标注