题意:给n(0 < n < 29)开关的初始和最终状态(01表示),以及开关之间的关联关系(关联关系是单向的输入a b表示a->b),问有几种方式得到最终的状态。否则输出字符字面值。
1.与poj 1222的区别:关联为单向,需要预处理出每个开关对自己的关联(开始在输入关联关系中处理自身的关联,WA了两发),操作的矩阵(变换的矩阵)为初始状态XOR最终状态;
2.处理完之后判断系数全为0的最终结果a[k][var]是否为0来判断是否无解。同时如有n个自由变元,由于每个变元只有两种状态,所以只有2^n个方案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
int a[][];
int equ,var;
int x[];
void debug()
{
int i,j;
rep0(i,,equ){
rep1(j,,var)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
int Guass()
{
int i,j,k,free_var = ,row,col;
for(row = ,col = ;row < equ && col < var;row++,col++){
int mx = row;
rep0(j,row+,equ)
if(abs(a[j][col]) > abs(a[mx][col])) mx = j;
if(a[mx][col] == ){
row--; // 行不变;
free_var++;
continue;
}
if(mx != row)
rep1(k,col,var)
swap(a[row][k],a[mx][k]);
rep0(j,row+,equ){
if(a[j][col]){ //第j盏灯也会对第i盏灯产生影响
rep1(k,col,var)
a[j][k] ^= a[row][k];
}
}
}
//debug();
for(;row < equ;row++)if(a[row][var] != ) return -; //无解;
if(free_var != ) return free_var;
rep_1(i,var-,){ //求解的变量的个数,并不是方程的个数;
x[i] = a[i][var];
rep0(j,i+,equ)
x[i] ^= (a[i][j] && x[j]); //第j个灯会影响到第i盏灯,同时第j盏灯也会亮。
}
return ;
}
void init()
{
int i,j,k,n;
MS0(a);MS0(x);
scanf("%d",&n);
equ = var = n;
int x,l,r;
rep0(i,,n) scanf("%d",&a[i][n]);
rep0(i,,n) scanf("%d",&x),a[i][n] ^= x;
rep0(i,,n) a[i][i] = ; //没有关联要格外赋值;
while(scanf("%d %d",&l,&r) == && l+r){
a[r-][l-] = ;
}
}
int main()
{
int T,kase = ,i;
cin>>T;
while(T--){
init();
int ret = Guass();
if(ret == -) puts("Oh,it's impossible~!!");
else printf("%d\n",<<ret);
}
return ;
}