Subtask #1全WA求调

Record

状压DP：

#include<cstdio>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char s;
	s=getchar();
	while(s<48||s>57)
	{
		if(s=='-')f=-f;
		s=getchar();
	}
	while(s>47&&s<58)
	{
		x=(x<<3)+(x<<1)+(s-48);
		s=getchar();
	}
	return x*f;
}
const int MOD=1e9,MAXNUM=(1<<12)+1;
int m,n;
int MAX,ans;
int p[13][MAXNUM],c[13],f[13][MAXNUM];
void prechk(int x,int t)
{
	int i,j;
	for(i=0;i<MAX;++i)
	{
		if((i&(i<<1))||(i&t))continue;
		p[x][++c[x]]=i;
	}
}
int main()
{
	int i,j,k,t,x;
	m=read();
	n=read();
	MAX=(1<<n);
	for(i=1;i<=m;++i)
	{
		for(j=1;j<=n;++j)
		{
			x=read();
			t=(t<<1)+(x^1);
		}
		prechk(i,t);
	}
	for(i=1;i<=c[1];++i)f[1][i]=1;
	for(i=2;i<=m;++i)
	{
		for(j=1;j<=c[i];++j)
		{
			f[i][j]=0;
			for(k=1;k<=c[i-1];++k)
			{
				if(p[i][j]&p[i-1][k])continue;
				f[i][j]=(f[i][j]+f[i-1][k])%MOD;
			}
		}
	}
	for(i=1;i<=c[m];++i)ans=(ans+f[m][i])%MOD;
	printf("%d",ans);
	return 0;
}