枚举它的每一行,对它状压一下就好
然后转移的时候要O(k) 所以预处理一下每个数字里由多少1就行了(考试时用了bitset 思想江化了)
#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<map> #include<set> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } #define inf 1000000007 #define mod 998244353 #define ll long long #define N 2010 int m,k; ll f[N*5][N],ans; int num[N]; int main() { register int i,j,o,x=0,tt; m=read();k=read(); int tp[13],t2[13]; for(i=1;i<=k;++i) x=x<<1|read(); f[1][x]=1; for(i=1;i<(1<<k);++i)num[i]=num[i>>1]+(i&1); for(i=1;i<(1<<k);++i)num[i]=(num[i]&1)?1:0; for(i=2;i<m-1;++i) { memset(tp,0,sizeof(tp)); memset(t2,0,sizeof(t2)); for(j=1;j<=k;++j)for(o=1;o<=k;++o) {x=read();tp[o]=tp[o]<<1|x;t2[j]=t2[j]<<1|x;} for(j=0;j<(1<<k);++j) { tt=x=0; for(o=1;o<=k;++o) {x=x<<1|num[j&tp[o]];tt=tt<<1|num[j&t2[o]];} (f[i][x]+=f[i-1][j])%=mod; (f[i][tt]+=f[i-1][j])%=mod; } } for(i=1,x=0;i<=k;++i) x=x<<1|read(); for(i=0;i<(1<<k);++i) {if(!num[i&x]){ans+=f[m-2][i];ans%=mod;}} printf("%lld\n",ans); return 0; }