Problem Description
There are N lamps in a line and M switches control them. Each switch is connected to a subset of these lamps. When a switch is flipped, all the lamps connected to it change its state (on to off and off to on).

Input
The input contains multiple test cases. Each test case starts with two integers N and M (0<N<=50, 0<M<=100), which stand for the number of lamps and swithes. Then M lines follows, each line contains N characters. The jth character of the ith line is '1' if the ith switch is connected to the jth lamp, and '0' otherwise. The next line is a integer Q, which is the number of queries. Each of following Q lines contains the initial and target state of lamps ('0' is off and '1' is on).

Output
For each query, output "Yes" if it is possible to change the state from initial to target with these swithes. Otherwise, output "No".

Sample Input
5 3
00000
10101
01010
3
00000 11111
10101 01010
11111 10001

Sample Output
Yes
Yes
No

1个回答

``````#include <stdio.h>
long long bstr_to_int(char* p,int len){
long long tmp=0;
for(int i=0;i<len;i++){
tmp<<=1;
if(*p++!='0')
tmp|=1;
}
return tmp;
}
int main(){
int n,m,q;
long long swithes[100];
char str1[50],str2[50];
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%s",str1);
swithes[i]=bstr_to_int(str1,n);
}
scanf("%d",&q);
for(int i=0;i<q;i++){
long long initial,target,halfway;
int status[100];
int prt=0;
scanf("%s %s",str1,str2);
initial=bstr_to_int(str1,n);
target=bstr_to_int(str2,n);
if(initial==target){
printf("Yes\n");
continue;
}
while(prt<m){
status[prt]^=1;
if(!status[prt]){
prt++;
continue;
}
halfway=initial;
for(int j=0;j<m;j++){
if(status[j])
halfway^=swithes[j];
}
if(halfway==target){
printf("Yes\n");
break;
}else{
prt=0;
continue;
}
}
if(prt>=m){
printf("No\n");
}

}
}
``````