C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 16096K, 提交时间: 2019-08-20 21:58:20

#include<bits/stdc++.h>

#define FOG(x,y,z) for(register int x=y,x##_=z;x<=x##_;++x)
#define DOG(x,y,z) for(register int x=y,x##_=z;x>=x##_;--x)
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EOD(x,y,z) for(int &x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)
#define While(x) for(;x;)
#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)

#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)

#define ts (*this)
#define sf scanf
#define pf printf

#define ll long long
#define ull unsigned long long
#define db double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)


using namespace std;

template<class T>bool tomin(T &x,T y){return y<x?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
	char c;
	x=0;
	int f=1;
	while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
	do x=(x<<3)+(x<<1)+(c^48);
	while(c=getchar(),c>='0'&&c<='9');
	x*=f;
}
bool mem1;
const db Pi=acos(-1);
const int P=100000007;
const int maxn=1e6+5;
int n,m;
namespace P20{
	int ans;
	void dfs(int x,int s,int p){
		if(x==m+1){
			ans+=s==0;
			return;
		}
		FOR(i,p,n-1)dfs(x+1,s^i,i+1);
	}
	void solve(){
		n=1<<n;
		dfs(1,0,1);
		pf("%d",ans);
	}
}
namespace P100{
	ll inv[maxn],pw;
	ll A,im;
	void Init(){
		pw=1;FOR(i,1,n)pw=(pw+pw)%P;
		A=pw=(pw-1+P)%P;
		im=inv[1]=1;FOR(i,2,m)im=im*(inv[i]=(P-P/i*inv[P%i]%P)%P)%P;
	}
	ll dp[maxn];
	void solve(){
		Init();
		dp[0]=1;
		dp[1]=0;
		FOR(i,2,m){
			dp[i]=(A-dp[i-1]+P)%P;
			dp[i]=(dp[i]-dp[i-2]*(i-1)%P*(pw-i+2)%P+P)%P;
			A=A*(pw-i+1)%P;
		}
		dp[m]=dp[m]*im%P;
		pf("%lld",dp[m]);
	}
}
int main(){
	// cerr<<(&mem2-&mem1)/1024.0/1024<<endl;
	srand(time(NULL));
	read2(n,m);
	if(n<=5)P20::solve();
	else P100::solve();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 43ms, 内存消耗: 16096K, 提交时间: 2020-04-01 22:41:20

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const ll mod=100000007;
ll n,m,ans=1;
ll fac[1000005],res[1000005];
inline ll ksm(ll x,ll k)
{
	if(k==1) return x;
	ll tmp=ksm(x,k>>1);
	if(k&1) return (tmp*tmp%mod)*x%mod;
	return tmp*tmp%mod;
}
int main()
{
	int i,j;
	scanf("%lld%lld",&n,&m);
	ll czy=ksm(2,n);
	czy=(czy+mod)%mod;
	fo(i,1,m-1)
	{
		ans=(ans*(czy-i))%mod;
		res[i+1]=((ans-res[i])%mod+mod)%mod;
		res[i+1]=(res[i+1]-(res[i-1]*(czy-i)%mod)*i%mod+mod)%mod;
		res[i+1]=(res[i+1]%mod+mod)%mod;
		res[1]=res[2]=0;
	}
	fac[0]=1;
	fo(i,1,m) fac[i]=fac[i-1]*i%mod;
	ans=(res[m]*ksm(fac[m],mod-2))%mod;
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}