Submission #18641234

---

Source Code Expand

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define mod 1000000007
#define int long long
using namespace std;
const int N=(1<<17);
int n,m,h,a[20],fac[N],inv[N],ans,cnt[20],dp[N];
inline void ck(int &a){a=(a>=mod)?a%mod:a;}
inline void add(int &a,int b){ck(b);a=((a+b>=mod)?a+b-mod:a+b);}
inline void del(int &a,int b){ck(b);a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){ck(b);a=(a*b)%mod;}
inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
signed main()
{
	n=read();m=read();h=(1<<n);
	for (int i=1;i<=m;i++) a[i]=read();
	fac[0]=1;
	for (int i=1;i<=h;i++) fac[i]=fac[i-1]*i%mod;
	inv[h]=m_pow(fac[h],mod-2);
	for (int i=h-1;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%mod;
	int full=(1<<n)-1;dp[0]=1;
	for (int i=m;i>=1;i--)
	{
		for (int mask=full;mask>=0;mask--)
		{
			for (int j=0;j<n;j++)
			{
				if ((mask>>j)&1||h-a[i]+1-mask<(1<<j)) continue;
				add(dp[mask|(1<<j)],dp[mask]*C(h-a[i]-mask,(1<<j)-1)%mod*fac[1<<j]%mod);
			}
		}
	}
	for (int mask=0;mask<=full;mask++)
	{
		int cnt=0;
		for (int i=0;i<n;i++) cnt+=((mask>>i)&1);
		if (cnt&1) del(ans,dp[mask]*fac[full^mask]%mod);
		else add(ans,dp[mask]*fac[full^mask]%mod);
	}
	mul(ans,h);
	printf("%lld\n",ans);
}

Submission Info

Judge Result