【题解】[HNOI2011] 卡农 线性 DP luoguP3214 —Qiuly

关于同种音乐的限制，最后直接让答案除上 $m!$ 即可。

现在我们需要算出选出 $m$ 的片段的方案数，考虑 $\rm{DP}$ ，设 $dp_i$ 表示前 $i$ 个片段已经确定，且满足下列要求：

• 这 $i$ 个片段中没有空集
• 这 $i$ 个片段互不相同
• 这 $i$ 个片段中所有的音符的出现次数全部都要是偶数次

现在考虑如何从 $dp_{i-1}$ 转移到 $dp_i$ 。

首先看第三个要求，不难发现在知道前 $i-1$ 个片段的情况下，$i$ 的音符集合一定是确定的—— $i$ 的音符集合一定是前 $i-1$ 个片段中出现次数为奇数的音符。也就是说 $i$ 的集合是随着前 $i-1$ 个片段变换的，已知选择前 $i-1$ 个片段的方案数为 $A_{2^n-1}^{i-1}$ ，那么 $i$ 的方案数也自然是 $A_{2^n-1}^{i-1}$ 。(注意该统计方案保证前 $i-1$ 个片段互不相同)

但是 $i$ 可能是空集，那么这个方案就不成立，方案不成立的个数当然是前 $i-1$ 个片段自由搭配且合法的情况数，那么自然就是 $dp_{i-1}$ ，为什么要计算和法的呢，因为首先计算了的方案数显然是满足第三个要求的，也就是说我们要去掉的也只能是满足第三个要求的不合法方案数，那么自然就是 $dp_{i-1}$ 个了。

最后考虑不满足第二种情况的方案数，首先我们令一个片段 $j$ 和 $i$ 一样 (在前 $i-1$ 个片段中最多一个和 $i$ 一样)，这个那么这样子我们将这两个片段都去掉的时候全局的方案数就是 $dp_{i-2}$ 了，因为剩下的一定是合法的。显然 $j$ 可以是前 $i-1$ 个片段中的任意一个，并且重复的音乐集的种类数为 $2^n-1-(i-2)$ ，为什么这么说呢，显然 $2^n-1$ 是非空集的音乐集方案数，$i-2$ 就是说剩下的 $i-2$ 个片段不重复，并且 $i,j$ 也不能与之重复，那么可供 $i,j$ 选择的就剩下 $2^n-1-(i-2)$ 个音乐集了。

也就是说，我们用 $A_{2^n-1}^{i-1}$ 减去这些不合法的方案后剩下的就是 $dp_i$ 了：

$$dp_i=A_{2^n-1}^{i-1}-dp_{i-1}-(dp_{i-2}\times(i-1)\times(2^n-1-(i-2)))$$

最后的答案就是 $dp_m$ 。

关于初始化的问题，首先 $dp_0=1$ ，那么选一个片段呢可以吗？其实不行，因为音符没有重复偶数次，所以一定是全都不合法的，又不允许空集的存在，也就是说 $dp_1=0$ 。用上面的式子从 $dp_2$ 推起即可。

Code:

#include <cstdio>
using namespace std;
typedef long long ll;

const int N=1e6+2;
#define p 100000007

int n,m;
ll dp[N],A[N];

inline ll pow(ll x,ll y,ll res=1) {
    for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
    return res%p;
}

int main() {
    scanf("%d%d",&n,&m);
    ll mul=pow(2,n)-1;mul=(mul%p+p)%p;
    A[0]=1;
    for(int i=1;i<=m;++i)
        A[i]=1ll*A[i-1]*(mul-i+1)%p;
    dp[0]=1,dp[1]=0;
    for(int i=2;i<=m;++i) {
        dp[i]=A[i-1]%p;
        dp[i]=(dp[i]-dp[i-1]+p)%p;
        dp[i]=(dp[i]-1ll*dp[i-2]*(i-1)%p*(mul-(i-2))%p+p)%p;
        dp[i]=(dp[i]%p+p)%p;
    }
    ll fac=1;
    for(int i=2;i<=m;++i) fac=1ll*fac*i%p;
    ll inv=pow(fac,p-2);
    printf("%lld\n",dp[m]*inv%p);
    return 0;
}