题解 P3214 【[HNOI2011]卡农】
StudyingFather
2020-07-24 00:06:05
题意看着挺绕的。
我们用二进制的方式来表示集合，在这样一个处理过后，题意变成了这样：有 $2^n-1$ 个数，分别为 $1,2,\ldots,2^n-1$，我们需要从中选一个大小为 $m$ 的**无序**子集，需要满足下面两种要求，求方案数：
1. 这 $m$ 个数两两不同（对应原来的“任意两个片段所包含的音阶集合都不同”的要求）；
2. 这 $m$ 个数的异或和为零（对应原来的“一段音乐中每个音阶被奏响的次数为偶数”的要求）。
我们设 $f_i$ 表示选了 $i$ 个数时，满足上面两种方案的**有序**集合的方案数。
如何计算？首先，如果我们已经确定了前 $i-1$ 个数，且这 $i-1$ 个数的异或和为 $x$，则第 $i$ 个数选 $x$ 即可。前 $i-1$ 个数的每一种合法方案对应一个 $x$，一共有 $A_{2^n-1}^{i-1}$ 种方案。
注意到这种选法可能会出现不合法的情况：
1. $x=0$，意味着前 $i-1$ 个数的异或和为零，显然有 $f_{i-1}$ 种方案。
2. $x$ 在之前出现过，我们设这个数是第 $j$ 个数，则将第 $i$ 和第 $j$ 个数删掉后，剩下 $i-2$ 个数构成一个满足要求的方案，而第 $i$ 个数有 $(2^n-1-(i-2))$ 种选法，再加上枚举 $j$ 的位置（共有 $i-1$ 种位置），一共有 $f_{i-2} \times (i-1) \times (2^n-1-(i-2))$ 种方案。
将上面两种不合法的情况减去即可。
注意我们求出的 $f$ 是**有序**集合下的答案，而所求答案为**无序**的，最后需要除以 $m!$。
```cpp
// Problem: P3214 [HNOI2011]卡农
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3214
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
#define MOD 100000007
using namespace std;
long long a[1000005],f[1000005];
int n,m;
long long fpow(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y&1)ans=ans*x%MOD;
x=x*x%MOD;
y>>=1;
}
return ans;
}
long long frac(int x)
{
long long ans=1;
while(x)
ans=ans*x%MOD,x--;
return ans;
}
int main()
{
cin>>n>>m;
int tot=fpow(2,n)-1;
a[0]=1;
for(int i=1;i<=m;i++)
a[i]=a[i-1]*(tot-i+1+MOD)%MOD;
f[0]=1;
for(int i=2;i<=m;i++)
{
f[i]=a[i-1];
f[i]=(f[i]-f[i-1]+MOD)%MOD;
f[i]=(f[i]-f[i-2]*(i-1)%MOD*(tot-(i-2))%MOD+MOD)%MOD;
}
cout<<f[m]*fpow(frac(m),MOD-2)%MOD<<endl;
return 0;
}
```