Submission #2698684

---

Source Code Expand

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
const int M=1000000007;
int c[22][22];
int f[2][533333]; 
int fir[20][533333];
int main()
{
	//freopen("zigzag.in","r",stdin);
	//freopen("zigzag.out","w",stdout);
	int n=io::F(),m=io::F(),k=io::F();
	if(n==1)puts("1"),exit(0);
	memset(c,-1,sizeof(c));
	for(register int i=1;i<=k;++i)
	{
		int a=io::F(),b=io::F(),v=io::F();
		if(c[a][b]==-1)c[a][b]=v;
			else if(c[a][b]!=v)puts("0"),exit(0);
	}
	for(register int i=1;i<1<<n-1;++i)
	{
		fir[n-1][i]=i&1<<n-2;
		for(register int j=n-2;j>=0;--j)
			fir[j][i]=i&1<<j?1<<j:fir[j+1][i];
	}
	int *x=f[0],*y=f[1];
	f[0][0]=1;
	for(register int i=1;i<=m;++i)
	{
		for(register int j=1;j<n;++j,std::swap(x,y),memset(y,0,sizeof(f[0])))
		{
			for(register int k=0;k<1<<n-1;++k)
				if(x[k])
				{
					if(c[i][j]!=1&&(k>>j-1&1)==0)
						(y[k]+=x[k])%=M; 
					if(c[i][j]!=0)
						(y[k^fir[j-1][k]^1<<j-1]+=x[k])%=M;
				}
		}
		//for(register int j=0;j<1<<n-1;++j)(y[0]+=x[j])%=M;
		//std::swap(x,y),memset(y,0,sizeof(f[0]));
	}
	int ans=0;
	for(register int i=0;i<1<<n-1;++i)(ans+=x[i])%=M;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result