https://www.acwing.com/problem/content/210/
要注意两点：开关之间的关系不一定是对称的，并且每个开关会控制自己。
消元的过程中可以计算出矩阵的秩，假如某个行没有主元但是有常数，那么就直接-1了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 40; bool a[MAXN + 5][MAXN + 1 + 5 ]; bool ans[MAXN + 5]; int Gauss_Jordan(int n) { int r = 0; for(int i = 1; i <= n; ++i) { int mx = i; for(int j = i; j <= n; ++j) { if(a[j][i]) { mx = j; break; } } if(!a[mx][i]) continue; ++r; if(mx != i) { for(int j = 1; j <= n + 1; ++j) swap(a[i][j], a[mx][j]); } for(int j = 1; j <= n + 1; ++j) { if(j != i && a[j][i]) { for(int k = 1; k <= n + 1; ++k) a[j][k] ^= a[i][k]; } } } for(int i = 1; i <= n; ++i) { if(a[i][i] == 0 && a[i][n + 1]) return -1; } /*for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n + 1; ++j) { printf(" %d", (int)a[i][j]); } printf("\n"); } puts("---\n");*/ for(int i = 1; i <= n; ++i) ans[i] = a[i][n + 1] & a[i][i]; return r; } int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); #endif // Yinku int T; scanf("%d", &T); while(T--) { memset(a, 0, sizeof(a)); int n; scanf("%d", &n); for(int i = 1, x; i <= n; ++i) { scanf("%d", &x); a[i][n + 1] = x; } for(int i = 1, x; i <= n; ++i) { scanf("%d", &x); a[i][n + 1] ^= x; } for(int i = 1; i <= n; ++i) a[i][i] = 1; int i, j; do { scanf("%d%d", &i, &j); if(i == 0 && j == 0) break; a[j][i] = 1; } while(1); /*for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n + 1; ++j) { printf(" %d", (int)a[i][j]); } printf("\n"); } puts("---\n");*/ int r = Gauss_Jordan(n); if(r == -1) puts("Oh,it's impossible~!!"); else printf("%lld\n", 1ll << (n - r)); } }AcWing - 208 - 开关问题 = 高斯消元法
标签：
原文地址：https://www.cnblogs.com/Inko/p/11528909.html