题意：n个灯，m个开关，给定每个开关控制的灯，全部的灯初始时全部熄灭，开关按一下其所控制的灯的状态全部反转，开关最多只能按一下。问达到目标状态的方案数。
思路：xor方程组的模型。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | /* ******************************************************************************** */#include <iostream> //#include <cstdio> //#include <cmath> //#include <cstdlib> //#include <cstring> //#include <vector> //#include <ctime> //#include <deque> //#include <queue> //#include <algorithm> //#include <map> //#include <cmath> //using namespace std; // //#define pb push_back //#define mp make_pair //#define X first //#define Y second //#define all(a) (a).begin(), (a).end() //#define fillchar(a, x) memset(a, x, sizeof(a)) // //typedef pair<int, int> pii; //typedef long long ll; //typedef unsigned long long ull; // //#ifndef ONLINE_JUDGE //void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);} //void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R> //void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1; //while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T> //void print(const T t){cout<<t<<endl;}template<typename F,typename...R> //void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T> //void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;} //#endif // ONLINE_JUDGE //template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);} //template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);} //template<typename T> //void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];} //template<typename T> //void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];} // //const double PI = acos(-1.0); //const int INF = 1e9 + 7; // ///* -------------------------------------------------------------------------------- */struct XorElimination { const static int maxn = 55; bool A[maxn][maxn]; int solve(int m, int n) { int i = 0, j = 0, k, r, u; while (i < m && j < n) { r = i; for (k = i; k < m; k ++) { if (A[k][j]) { r = k; break; } } if (A[r][j]) { if (r != i) for (k = 0; k <= n; k ++) swap(A[r][k], A[i][k]); for (int u = i + 1; u < m; u ++) { if (A[u][j]) { for (k = i; k <= n; k ++) A[u][k] ^= A[i][k]; } } i ++; } j ++; } /** 返回自由变元个数，无解返回-1 **/ for (int i = 0; i < m; i ++) { if (A[i][n]) { bool ok = false; for (int j = 0; j < n; j ++) { if (A[i][j]) { ok = true; break; } } if (!ok) return -1; } } return n - i; }};/** 下标从0开始 **/XorElimination solver;bool buf[55][55];int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int T, n, m, cas = 0; cin >> T; while (T --) { cin >> n >> m; memset(buf, 0, sizeof(buf)); for (int i = 0; i < m; i ++) { int x, y; scanf("%d", &x); for (int j = 0; j < x; j ++) { scanf("%d", &y); buf[y - 1][i] = true; } } printf("Case %d:
", ++ cas); int q; cin >> q; while (q --) { for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { solver.A[i][j] = buf[i][j]; } } for (int i = 0; i < n; i ++) { int x; scanf("%d", &x); solver.A[i][m] = x; } int r = solver.solve(n, m); cout << (~r? (1ll << r) : 0) << endl; } } return 0;}/* ******************************************************************************** */ |