题意：从编号为 1~N 的音阶中可选任意个数组成一个音乐片段，再集合组成音乐篇章。要求一个音乐篇章中的片段不可重复，都不为空，且出现的音符的次数都是偶数个。问组成 M 个片段的音乐篇章有多少种。答案取模1000000007（质数）。
解法：先将题目模型化：N 个数组成 M 种组合，且要求组合之间互不相等，把各组合用二进制表示对 N 个数的取舍状态之后的异或和为0。 虽然求得是组合，但我们转化为排列来做计算时更方便。假设 f[i] 表示从 n 个数中选 i 种排列的方案数。那么就是“总的排列数 - 第 i 个片段为空（0）- 第 i 个片段与之前的 i-1 个片段中的一个重复”，而组合数就只需再除以“ i ! ”。由于递推的思想，我们只考虑第 i 个片段，之前的状态用 f[ ] 表示。
于是，f[i] = P(2^n-1,i-1) （由于要求异或和为0，据前 i-1 个片段就能确定第 i 个片段的状态了） - f[i-1] （组成 i-1 个片段的方案数） - (i-1) * [2^n-1-(i-2)] * f[i-2] 。（乘法原理｛分步｝，位置、唯一的重复的状态、排列数）另外，P(n,m)=n!/(n-m)!，所以 P(n,i)=n!/(n-i)!=n!/[n-(i-1)] * (n-(i-1))=P(n,i-1)*[n-(i-1)]。
由于模的数是质数，可利用费马小定理求逆元。我昨天的一篇博文有提到：1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define mod 100000007 8 #define N 1000010 9 typedef long long LL;10 11 LL f[N],P[N];12 LL qpow(LL x,int k)13 {14 LL ret=1;15 while (k)16 {17 if (k&1) ret=(ret*x)%mod;18 x=(x*x)%mod, k>>=1;19 }20 return ret;21 }22 LL ny(LL x) { return qpow(x,mod-2);}23 int main()24 {25 int n,m; LL p,mm=1;26 scanf("%d%d",&n,&m);27 p=(qpow(2,n)-1+mod)%mod;28 P[0]=1, f[0]=1;29 P[1]=p, f[1]=0;//f[1]=0;30 for (int i=2;i<=m;i++)31 {32 f[i]=((P[i-1]-f[i-1]+mod)%mod-((i-1)*(p-(i-2))%mod*f[i-2])%mod+mod)%mod;33 P[i]=(P[i-1]*((p-i+1)+mod)%mod)%mod;34 mm=(mm*i)%mod;35 }36 printf("%lld\n",(f[m]*(ny(mm)%mod))%mod);37 return 0;38 }