题意 : 

给你n个音阶，要求组成一个长m个片段的音乐有多少方案。

每个片段里每种音阶至多含有一个，任意两个片段包含的音阶不能完全相同，并且每一种音乐里每个音阶出现的次数必须是偶数次。

两个音乐不同的话当且仅当不存在任意一种对应方案使a包含的片段与b包含的片段完全相同。

eg. {

{1,2}，{2,3}}与{

{2,3},{1,2}}是相同的音乐。（虽然都不是合法的音乐

数据范围 ：

n，m <= 1000000

----------------------------------------------------------------此后一千里----------------------------------------------------------

 

 

 

 

 

 

 

 

 

 

 

 

 

我们考虑如果选定了m - 1个片段，那么最后一个片段显然已经确定了，因为每种音阶必须出现偶数次

所以我们从所有2^n - 1中片段中选出m - 1个的方案就是C(2^n - 1,m - 1) 

那么算多了的方案就是选出了m - 1个片段已经是合法音乐，那么我们加入的最后一个片段就会是空集，这个要减掉

还有最有一个片段如果与之前的片段有重复，那么去掉这两个相同的片段，剩下的一定是个合法音乐，这两个片段就有 2^n - 1 - (m - 2)中选择方案

然后递推式 : f[i] = (C(2^n - 1,m - 1) - f[i - 1] - f[i - 2] * (2^n - m + 1) )/ i

除 i 是因为每一种合法方案被计算了 i 次

ps : 自己想的时候一直在想怎么容斥掉有相同的情况，发现没法容斥，没想到直接去搞组合数就可以了。。。。

代码 ： 

/*Lelouch vi Britannia here commands you , all of you , die !*/#include
      
       #define INF 0x3f3f3f3f#define low(x) ((x)&(-(x)))#define LL long long#define eps 1e-9#define MOD 100000007using namespace std;#define int intinline int Max(int a,int b) {
    return a>b?a:b;}inline int Min(int a,int b) {
    return a
       
        0?a:-a;}inline int Sqr(int a) {
    return a*a;}#undef int#define MAXN 1000006int n,m;LL two[MAXN],C[MAXN],f[MAXN],ni[MAXN];void Pre() {    two[0]=1;C[0]=1;ni[1]=1;    for(int i=1;i<=n;i++) two[i]=two[i-1]*2%MOD;    for(int i=2;i<=m;i++) ni[i]=(MOD-MOD/i)*ni[MOD%i]%MOD;    for(int i=1;i<=m;i++) C[i]=C[i-1]*(MOD+two[n]-i)%MOD*ni[i]%MOD;} int main() {    scanf("%d%d",&n,&m);    Pre();    if(C[m-1]<2||!m) f[m]=0;    else {        f[0]=1;        for(int i=2;i<=m;i++) {            f[i]=((C[i-1]-f[i-1]-f[i-2]*(MOD+two[n]-i+1)%MOD)%MOD+MOD)%MOD;            f[i]=f[i]*ni[i]%MOD;        }    }    printf("%lld\n",f[m]);    return 0;}/*Hmhmhmhm . That's right , I am killer.*/