题目描述

输入

输出

样例输入

样例输出

提示

<span style="font-size:18px;">#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long 
using namespace std;
const int maxn=1000006;
const int mod=100000007;
int n,m;
ll f[maxn],g[maxn],Pow,d,x,y;
inline int get(){char c;while(!isdigit(c=getchar()));int v=c-48;while(isdigit(c=getchar()))v=v*10+c-48;return v;
}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}else{ll tmp=exgcd(b,a%b,x,y);ll t=x;x=y;y=t-(a/b)*y;return tmp;}
}
inline ll power(int a,int b){ll ret=1,tmp=a;while(b){if(b&1)ret=ret*tmp%mod;tmp=tmp*tmp%mod;b>>=1;}return ret;
}
int main(){n=get();m=get();Pow=power(2,n)%mod;  g[0]=1;f[0]=f[1]=f[2]=0;for(int i=1;i<=m;++i)g[i]=g[i-1]*(Pow-i)%mod;ll i;for(i=3;i<=m;++i){f[i]=g[i-1]-f[i-1]-(i-1)*(Pow+1-i)%mod*f[i-2]%mod;f[i]%=mod;}if(f[m]<0)f[m]+=mod;d=1;for(int i=1;i<=m;++i)d=d*i%mod;exgcd(d,mod,x,y);d=(x%mod+mod)%mod;f[m]=d*f[m]%mod;printf("%lld\n",f[m]);return 0;
}</span>

思路：由数学知识可知总共有2^n-1个集合，f[ i ]为取i个集合的合法方案，g[ i ]为取i个集合的总方案（包括不合法的），因为音阶要取偶数个，所以第m个方案可由前m-1的方案决定。即f[ i ]为g[ i-1 ]-♂（某个数）。原来是无序，现在我们假设它有序，最后再用乘法逆元求（f[ m ]/m!）mod MOD。

这♂是什么呢

        “不合法的那些方案，不合法的方案有两种： 
1、前i−1段的方案是合法的，这时前i−1段，每种音调的个数是偶数个，而加入第i段后，由于第i段中每种不同的音调都只能出现1次，那么加入第i段后每种音调的个数可能出现奇数个，就不合法了，这种情况的方案数有f[i−1]种 
2、第i段和前i−1段中某一段是相同的，为了便于叙述，我们说前i−1段中与第i段相同的段是第i段的冲突对象，那么冲突对象可以在1到i−1号段中选一个，有(i−1)种选法，选好冲突对象后，剩下的i−2个不冲突的段的方案数是f[i−2](有2个子集被去掉了，某些种音调里去掉了偶数次，现在每种音调的出现次数就是偶数次，那么剩下的段肯定是合法的),第i段和其冲突对象对应的子集有(2n−1)−(i−2),解释：n个音调的子集总数共有(2n−1)种，然后前i−1段中有i−2个不和第i段相同的段已经确定下来了，占用了其中的i−2个子集，因此前面的式子是(2n−1)−(i−2)，因此乘法计数可以得到二号情况的方案数是f[i−2](i−1)[(2n−1)−(i−2)] 
那么就能得到初步的一个递推式： 
f[i]=Ai−12n−1−f[i−1]−f[i−2](i−1)[(2n−1)−(i−2)] 
然后用g[i]代进去替换掉那个A 
f[i]=g[i−1]−f[i−1]−f[i−2](i−1)[(2n−1)−(i−2)]”