题意：从编号为 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)]。
由于模的数是质数，可利用费马小定理求逆元。我昨天的一篇博文有提到：【poj 1284】Primitive Roots（数论--欧拉函数 求原根个数）｛费马小定理、欧拉定理｝
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #include<iostream>
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 }