ai取值范围0~1,xi取值范围0~3,所以最后异或的结果不会超过两位二进制。所以可以用一个60位的数保存30个式子的值，然后m的范围是小于22，二分一下就可以了，4^11=4*10^6，结果存下来排个序然后二分找一下就可以了。
#include <stdio.h> #include <string.h> #include <algorithm> typedef __int64 LL; int cas,n,m,ai[35][30],si[30][4]; LL ans,tmp[1<<22+2]; int sum[1<<22+2]; int size,nsize; int binser(LL x){ int low=0,high=size,mid; for(;;){ mid=(low+high)/2; if(mid==low)break; if(tmp[mid]<=x)low=mid; else high=mid; } return tmp[mid]==x?sum[mid]:0; } LL cal(int p,int x){ LL ans=0; for(int i=1;i<=n;i++) ans=(ans<<2)+(ai[i][p]*x); return ans; } void dfs(int p,LL now,int full,int id){ if(p>full)id==0?tmp[size++]=now:ans+=binser(now); else for(int i=1;i<=si[p][0];i++) dfs(p+1,now^cal(p,si[p][i]),full,id); } int main(){ //freopen("test.in","r",stdin); scanf("%d",&cas); while(cas--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&ai[i][j]); for(int i=1;i<=m;i++){ scanf("%d",&si[i][0]); for(int j=1;j<=si[i][0];j++){ scanf("%d",&si[i][j]); } } ans=size=0; int halfm=m/2; dfs(1,0LL,halfm,0); std::sort(tmp,tmp+size); nsize=size,size=1,sum[0]=1; for(int i=1;i<nsize;i++){ if(tmp[i]!=tmp[i-1]){ tmp[size]=tmp[i],sum[size]=1,size++; }else sum[size-1]++; } dfs(halfm+1,0LL,m,1); printf("%I64d\n",ans); } return 0; }