题解 P3214 【[HNOI2011]卡农】

· · 题解

题目分析

假如题目没有每个音阶被奏响的次数为偶数的限制，则答案就是 C_{2^n-1}^m。
加上这个限制后，我们可以发现，一旦确定了前 m-1 个集合，则最后一个集合就是确定的。因为如果一个音阶在前 m-1 个集合出现的次数是奇数次，它就必须在最后一个集合中出现；如果出现的次数是偶数次，就必须不出现在最后一个集合中。这样我们就有了答案 C_{2_n-1}^{m-1}。
但是容易发现如果所有音阶在前 m-1 个集合中出现了偶数次，则最后一个集合就是空集，不合法。同时最后一个集合也可能在前m-1个集合中重复。
怎么去掉不合法的方案呢？我们令 f_i 表示 i 个集合时满足题目条件的方案数（组合），那么就可以发现对于 i ，出现空集的方案数就是 f_{i-1}，因为它就等于前 i-1 个集合所有音阶出现次数为偶数的方案数；出现重复集合的方案数就是 f_{i-2}*(2^n-1-(i-2))，因为它就等于前 i-2 个集合所有音阶出现次数为偶数的方案数再乘以没被选过的集合的数量。
同时因为每种方案都重复了 i 次，所以还要再除以 i。
那么我们就得出了递推式 f_i=\dfrac{C_{2_n-1}^{i-1}-f_{i-1}-f_{i-2}*(2^n-1-(i-2))}{i}
直接递推就好了！

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+(c&15),c=getchar();
}
#define P 100000007
#define N 1000001
int n,m,x,f[N],C;
inline int ksm(int a,int b=P-2)//快速幂
{
    int s=1;
    for(;b;b>>=1,a=(long long)a*a%P)if(b&1)s=(long long)s*a%P;
    return s;
}
signed main()
{
    read(n),read(m),x=ksm(2,n)-1;
    if(x<0)x+=P;
    C=(long long)x*(x+P-1)%P*ksm(2)%P;
    for(register int i=3;i<=m;i++)
    {
        f[i]=((C-f[i-1]-(long long)f[i-2]*((x-i+2+P)%P)%P)%P+P)%P*ksm(i)%P,C=(long long)C*(x-i+1+P)%P*ksm(i)%P;
    }
    printf("%d\n",f[m]);
    return 0;
}