BZOJ 2339: [HNOI2011]卡农 – [递推/容斥]


题目传送门(BZOJ)

题解 :

今天靠这道题救了我垫底的命 233
我们先令求出的答案是有序的, 那么最后除以一个 $M!$ 也就是乘一个 $M!^{-1}\mod 19961993$ 即可
设状态 F[i] 为在长度为 $i$ 时合法的有序方案数
长度为 $i$ 时的总方案数量是 $A_{2^n-1}^{i-1}$ 个,
之所以是 $i-1$ 是因为当前 $i-1$ 个确定了时, 为了满足出现偶数次的条件, 第 $i$ 个也随之确定了.
然后开始斥掉不合法的方案
首先, 若前 $i-1$ 个已经合法, 那么第 $i$ 个只能是空集, 这是不合法的, 所以要减掉 $F[i-1]$
然后当第 $i$ 个和前面某一个重复的时候, 也不合法
前面共有 $i-1$ 个位置, 我们先把 $i-1$ 这个系数放在这里, 考虑对于单个位置有多少个会和第 $i$ 个位置重复的
首先我们要求这前 $i-1$ 个, 去掉这个重复的 $x$ 一定是合法的
原因是因为加上了 $i$ 合法, 那么对于 $i$ 和 $x$ 因为重复所以若某位有音阶就一定有两个, 减去偶数个仍合法
那么就是 $F[i-2]$ 种合法的方案了.
在 $F[i-2]$ 种合法的方案里, 这个位置还可以有 $(2^n-1)-(i-2)$ 种取值(把另外 $i-2$ 个已经取得去掉)
$\therefore F[i] = A_{2^n-1}^{i-1} – (F[i-1] + (i-1)\times F[i-2]\times (2^n-1)-(i-2))$
我们 $O(N)$ 递推出 $F[M]$, 然后乘一个 $M!$ 的逆元即可

代码 :

#include <cstdio>
#define ll long long
const int p = 1e8+7;
inline ll qp(ll x, int y) {
    ll res = 1;
    for(; y; y >>= 1, x = (ll)x*x%p) if(y&1) res = (ll)res*x%p;
    return res;
}
ll A[1000010], f[1000010];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    int tmp = qp(2, n)-1; if(tmp < 0) tmp += p;
    A[0] = 1;
    for(int i = 1; i <= m; i ++ ) A[i] = (A[i-1]*(((ll)tmp-i+1+p)%p))%p;
    for(int i = 3; i <= m; i ++ ) f[i] = (A[i-1]-f[i-1]-(f[i-2]*(i-1)%p*(tmp-i+2)%p)+p)%p;
    ll fac = 1;
    for(int i = 2; i <= m; i ++ ) fac = fac*i%p;
    f[m] = f[m]*qp(fac, p-2)%p;
    printf("%lld\n", (f[m]+p)%p);
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

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