开关问题
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 8714 | Accepted: 3424 |
Description
有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)
Input
输入第一行有一个数K,表示以下有K组测试数据。
每组测试数据的格式如下:
第一行 一个数N(0 < N < 29)
第二行 N个0或者1的数,表示开始时N个开关状态。
第三行 N个0或者1的数,表示操作结束后N个开关的状态。
接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。
每组测试数据的格式如下:
第一行 一个数N(0 < N < 29)
第二行 N个0或者1的数,表示开始时N个开关状态。
第三行 N个0或者1的数,表示操作结束后N个开关的状态。
接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。
Output
如果有可行方法,输出总数,否则输出“Oh,it's impossible~!!” 不包括引号
Sample Input
2 3 0 0 0 1 1 1 1 2 1 3 2 1 2 3 3 1 3 2 0 0 3 0 0 0 1 0 1 1 2 2 1 0 0
Sample Output
4 Oh,it's impossible~!!
Hint
第一组数据的说明:
一共以下四种方法:
操作开关1
操作开关2
操作开关3
操作开关1、2、3 (不记顺序)
一共以下四种方法:
操作开关1
操作开关2
操作开关3
操作开关1、2、3 (不记顺序)
题目链接:POJ 1830
比较裸的一道题,记得开关自己跟自己是有关系的,即Mat[i][i]要恒为1,用高斯消元在判断了自由变量之后如果还出现非0系数,则说明无解,如果有解即有$freenum$个自由变量,那么显然每一个自由变量是随意取值的,每一个都取0或1,那么答案显然是$2^{freenum}$个
如何列方程呢?两边同时异或一下开始的状态即可以得到目标的状态,因为S->T的操作和0->(S xor T)的操作是一样的
代码:
#include <stdio.h> #include <iostream> #include <algorithm> #include <cstdlib> #include <sstream> #include <numeric> #include <cstring> #include <bitset> #include <string> #include <deque> #include <stack> #include <cmath> #include <queue> #include <set> #include <map> using namespace std; #define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define fin(name) freopen(name,"r",stdin) #define fout(name) freopen(name,"w",stdout) #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); typedef pair<int, int> pii; typedef long long LL; const double PI = acos(-1.0); const int N = 31; int Mat[N][N]; int Gaussian(int ne, int nv) { int ce, cv, i, j; for (ce = 1, cv = 1; ce <= ne && cv <= nv; ++ce, ++cv) { int te = ce; for (i = ce + 1; i <= ne; ++i) if (Mat[i][cv] > Mat[te][cv]) te = i; if (te != ce) { for (i = cv; i <= nv + 1; ++i) swap(Mat[ce][i], Mat[te][i]); } if (!Mat[ce][cv]) { --ce; continue; } for (i = ce + 1; i <= ne; ++i) { if (Mat[i][cv]) { for (j = cv; j <= nv + 1; ++j) Mat[i][j] ^= Mat[ce][j]; } } } for (i = ce; i <= ne; ++i) if (Mat[i][cv]) return -1; return nv - (ce - 1); } int main(void) { int tcase, n, i; scanf("%d", &tcase); while (tcase--) { CLR(Mat, 0); scanf("%d", &n); for (i = 1; i <= n; ++i) { scanf("%d", &Mat[i][n + 1]); Mat[i][i] = 1; } for (i = 1; i <= n; ++i) { int x; scanf("%d", &x); Mat[i][n + 1] ^= x; } int a, b; while (~scanf("%d%d", &a, &b) && (a || b)) Mat[b][a] = 1; int frnum = Gaussian(n, n); frnum == -1 ? puts("Oh,it's impossible~!!") : printf("%d ", 1 << frnum); } return 0; }