关于同种音乐的限制,最后直接让答案除上 $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;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

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