直接T了，居然可以这么剪枝
题解链接：点我
1 #include<cstdio> 2 #include<map> 3 #include<cstring> 4 #define ll __int64 5 using namespace std; 6 ll a[23],x[23][5],ans; 7 map<ll,ll>p; 8 void dfs(int d,int n,ll res,int f) 9 { 10 if(d==n){ 11 if(f) p[res]++ 12 if(res==0) ans++; 13 return ; 14 } 15 for(int i=1;i<=x[d][0];i++) 16 { 17 ll temp=x[d][i]&a[d]; 18 dfs(d+1,n,temp^res); 19 } 20 } 21 int main() 22 { 23 int t,i,j,n,m,k; 24 ll temp=3,te; 25 #ifndef ONLINE_JUDGE 26 freopen("1.in","r",stdin); 27 #endif 28 scanf("%d",&t); 29 while(t--){ 30 scanf("%d%d",&n,&m); 31 memset(a,0,sizeof(a)); 32 memset(x,0,sizeof(x)); 33 p.clear(); 34 for(i=0;i<n;i++) 35 for(j=0;j<m;j++){ 36 scanf("%I64d",&te); 37 if(te) 38 a[j]|=(temp<<(2*i)); 39 } 40 for(i=0;i<m;i++){ 41 scanf("%d",&x[i][0]); 42 for(j=1;j<=x[i][0];j++){ 43 scanf("%I64d",&te); 44 x[i][j]=te; 45 for(k=1;k<n;k++){ 46 x[i][j]|=(te<<(2*k)); 47 } 48 } 49 } 50 dfs(0,m/2,0,1); 51 dfs(m/2,m,0,0); 52 printf("%I64d ",ans); 53 } 54 return 0; 55 }