hdu3364 Lanterns 高斯消元
//有m個開關，n個燈泡，每個開關可以控制不同的燈泡(可以有多個)
//給定n個燈泡的亮暗情況，問有多少種開關的情況
//用a[i][j]表示第j個開關對第i個燈泡能否控制，1為能，0為否
//用高斯消元，ans = 2^(var-k) ,(var-k)為自由變量數
#include
#include
#include
using namespace std ;
const int maxn = 60 ;
#define abs(a) (a > 0 ? a : -a)
typedef __int64 ll ;
int a[maxn][maxn] ;
int b[maxn][maxn] ;
int x[maxn] ;
int free_x[maxn] ;
int equ , var;
int Gauss()
{
memset(free_x , 0 , sizeof(free_x)) ;
int free_num , free_idex ;
int col = 0 ;int k ;
for(k = 0;k < equ && col < var;k++,col++)
{
int max_r = k ;
for(int i = k+1;i < equ ;i++)
if(abs(a[max_r][col])< abs(a[i][col]))
max_r = i ;
if(max_r != k)
for(int j = 0;j <= var;j++)
swap(a[max_r][j] , a[k][j]) ;
if(a[k][col] == 0){k--;continue ;}
for(int i = k+1 ; i < equ ;i++)
{
if(a[i][col] == 0)continue ;
for(int j = col ; j <= var;j++)
a[i][j] ^= a[k][j] ;
}
}
for(int i = k ;i < equ ;i++)
if(a[i][col] != 0)return -1 ;//無解
return var - k ;
}
int main()
{
//freopen("in.txt" , "r" , stdin) ;
int T ;int cas =0 ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%d%d" , &equ , &var) ;
memset(a , 0 , sizeof(a)) ;
for(int i = 0;i < var;i++)
{
int num ;
scanf("%d" , &num) ;
while(num--)
{
int t ;
scanf("%d" , &t) ;
a[t-1][i] = 1;
}
}
int q ;
for(int i = 0 ;i < equ ;i++)
memcpy(b[i] , a[i] , sizeof(a[i])) ;
scanf("%d" , &q) ;
printf("Case %d:\n" , ++cas) ;
while(q--)
{
for(int i = 0 ;i < equ ;i++)
{
int t ;
scanf("%d" , &t) ;
b[i][var] = t ;
}
for(int i = 0 ;i < equ;i++)
memcpy(a[i] , b[i] , sizeof(b[i])) ;
int sum = Gauss() ;
if(sum < 0){puts("0");continue ;}
ll ans = 1;
for(int i = 1;i <= sum;i++)
ans*=2;
printf("%I64d\n" , ans) ;
}
}
return 0 ;
}
