Submission #3188018

---

Source Code Expand

#include<bits/stdc++.h>
#define gc getchar()
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int
using namespace std;
const int mod = 1e9+7;
inline int read(){char ch=gc;int w=1,s=0;while(!isdigit(ch)){if(ch=='-') w=-1;ch=gc;};while(isdigit(ch)){s=s*10+ch-'0';ch=gc;} return w*s;}
int A[100010],n,m,fac[2000010],Ifac[2000010];
int f[18][1<<17];
inline int C(int p,int q)
{
	return 1ll*fac[p]*Ifac[q]%mod*Ifac[p-q]%mod;
}
inline ll ksm(ll x,ll y){ll res=1; while(y){if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;} return res;}
inline void Init()
{
	Ifac[0]=1;fac[0]=1;
	for(rint i=1;i<=2e6;++i) fac[i]=1ll*fac[i-1]*i%mod;
	Ifac[2000000]=ksm(fac[2000000],mod-2);
	for(rint i=(2e6)-1;i;--i) Ifac[i]=1ll*Ifac[i+1]*(i+1)%mod;
}inline bool cmp(int a,int b) {return a>b;}
inline ll add(ll a,ll b){a+=b;if(a>=mod) a-=mod;return a;}
int main()
{
	n=read(),m=read();
	for(rint i=1;i<=m;++i) A[i]=read();
	sort(A+1,A+m+1,cmp);Init();
	f[0][0]=1;int Max=1<<n;
	for(rint i=1;i<=m;++i)
	{
		for(rint j=0;j<Max;++j) f[i][j]=add(f[i][j],f[i-1][j]);
		for(rint j=0;j<Max;++j)
		{
//			int total=0;
//			for(rint k=1;k<=n;++k)
//			{
//				if((1<<k-1)&j) total+=(1<<k-1);
//			}
			int rest=(1<<n)-j-A[i];
			for(rint k=1;k<=n;++k)
			{
				if((1<<k-1)&j) continue;
				else 
				{
					if((1<<k-1)-1>rest) continue;
					f[i][j|(1<<k-1)]=add(f[i][j|(1<<k-1)],1ll*f[i-1][j]*C(rest,(1<<k-1)-1)%mod*fac[1<<k-1]%mod);
				}
			}
		}
	}ll res=0;
	for(rint i=0;i<Max;++i)
	{
//		cout<<f[m][i]<<"\n";
		int cnt=__builtin_popcount(i);
		if(cnt&1)
		{
			res=add(res,mod-1ll*f[m][i]*fac[ksm(2,n)-i-1]%mod);
		}
		else res=add(res,1ll*f[m][i]*fac[ksm(2,n)-i-1]%mod);
	}cout<<1ll*res*ksm(2,n)%mod<<"\n";
	return 0;
}

Submission Info

Judge Result