2018-02-02 10:09:17

$dp[i]=A_{2^n-1}^{i-1}-dp[i-1]-(dp[i-2]*(i-1)*(2^n-1-(i-2)))$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
T f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
x*=f;
}

typedef long long LL;
const int maxn=1000010,mod=100000007;
int n,m;
LL dp[maxn],inv,A[maxn],mx;

LL power(LL x,LL y){
LL res=1;
for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
return res;
}

int main(){
read(n);read(m);
inv=A[0]=1;
For(i,2,m) inv=inv*i%mod;
inv=power(inv,mod-2);
mx=power(2,n)-1;
For(i,1,m) A[i]=A[i-1]*(mx-i+1)%mod;
dp[0]=1;
For(i,2,m){
dp[i]=A[i-1]-dp[i-1]+mod;
dp[i]-=dp[i-2]*(i-1)%mod*(mx-(i-2))%mod;
dp[i]=(dp[i]%mod+mod)%mod;
}
printf("%lld\n",dp[m]*inv%mod);
return 0;
}
• star
首页