Submission #18988207

---

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
using namespace std;
const int N=25;
int n,m,k,lim[N][N],dp[2][1<<21];
inline void add(int &a,int b){a=((a+b>=mod)?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=1ll*a*b%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;
}
inline int lowbit(int x){return x&(-x);}
signed main()
{
	n=read()-1;m=read();k=read();
	memset(lim,-1,sizeof(lim));
	for (int i=1;i<=k;i++)
	{
		int a=read(),b=read()-1,c=read();
		lim[a][b]=c;
	}
	int full=(1<<n)-1;
	for (int mask=0;mask<=full;mask++)
	{
		bool bl=1;
		for (int i=0;i<n;i++)
		{
			if (lim[1][i]==-1) continue;
			if (lim[1][i]!=((mask>>i)&1))
			{
				bl=0;
				break;
			}
		}
		if (bl) dp[0][mask]=1;
	}
	int cur=1;
	for (int i=2;i<=m;i++)
	{
		for (int j=0;j<n;j++)
		{
			memset(dp[cur],0,(1<<n)*sizeof(int));
			for (int mask=0;mask<=full;mask++)
			{
				if (!dp[cur^1][mask]) continue;
				if (lim[i][j]!=1&&(mask>>j)%2==0) add(dp[cur][mask],dp[cur^1][mask]);
				if (lim[i][j]!=0)
				{
					if ((mask>>j)&1){add(dp[cur][mask],dp[cur^1][mask]);continue;}
					int s=mask>>(j+1),t=(mask&((1<<(j+1))-1));
					if (!s) add(dp[cur][mask|(1<<j)],dp[cur^1][mask]);
					else
					{
						s-=lowbit(s);s=(s<<(j+1))|t;s|=(1<<j);
						add(dp[cur][s],dp[cur^1][mask]);
					}
				}
			}
			// for (int mask=0;mask<=full;mask++) printf("%d ",dp[cur][mask]);
			// printf("\n");
			cur^=1;
		}
	}
	cur^=1;
	int ans=0;
	for (int mask=0;mask<=full;mask++) add(ans,dp[cur][mask]);
	printf("%d\n",ans);
}

Submission Info

Judge Result