[USACO06NOV]Corn Fields G

题目传送门

解题思路

这题就用一个f[i][s[j]]
表示在当前第 i 行的状态为 s[i]
f [ i ] [ s [ j ] ] + = f [ i − 1 ] [ s [ w ] ] f[i][s[j]]+=f[i−1][s[w]] f[i][s[j]]+=f[i−1][s[w]]

注：要取模

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,x,t,answer,a[15],b[10005],f[15][10005];
int main()
{
   
	scanf("%lld%lld",&n,&m);
	for(long long i=0;i<=(1<<m)-1;i++)//初值
	 if(((i<<1)&i)==0)b[++t]=i;
	for(long long i=1;i<=n;i++)//初值
	 for(long long j=1;j<=m;j++)
	 {
   
	  	scanf("%lld",&x);
		a[i]=(a[i]<<1)+x;
	 }
	f[0][0]=1;//初值
	for(long long i=1;i<=n;i++)//dp
	 for(long long j=1;j<=t;j++)
	  if((a[i]&b[j])==b[j])//特判
	   for(long long k=1;k<=t;k++)
		if((b[j]&b[k])==0)//特判
		 f[i][b[j]]=(f[i][b[j]]+f[i-1][b[k]])%100000000;//状态转移
	for(long long i=1;i<=t;i++)//累加
	 answer=(answer+f[n][b[i]])%100000000;
	printf("%lld",answer%100000000);//取模
	return 0;
}

谢谢