#include #include #include using namespace std; constexpr int INF = 987654321; // 戻り値 // ひとつめ: status(int) 0: 解なし, 1: 解が一意に決まった, 2: 解が複数あって一意に決まらない // ふたつめ: cnt(int): 手数。解が複数あるときは最小手数。 // みっつめ: arr(vector): 解。複数あるときはそのうちのどれかひとつ tuple> mod2_gauss_elimination(const vector> &A, const vector &b) { const int n = A.size(); vector> B(n, vector(n+1)); for(int i=0; i v; for(int r=curr; r arr; for(int mask=0; mask<1<<(n-curr); ++mask) { v.assign(n, -1); // -1 は任意を表す int cnt = __builtin_popcount(mask); for(int r=curr, k=0; r>=0 && cnt> k++ & 1; } v[i] ^= v[c] & B[r][c]; } if(v[i]) { ++cnt; } } if(mini > cnt) { mini = cnt; // arr = v; } } return make_tuple(2, mini, arr); } // 解が一意に決まる。普通に後退代入 v.assign(n, 0); for(int r=n-1; r>=0; --r) { v[r] = B[r][n]; for(int c=n-1; c>r; --c) { v[r] ^= v[c] & B[r][c]; } } int cnt = 0; for(int i=0; i b(n); for(int r=0; r> A(n, vector(n)); for(int r=0; r _; tie(status, cnt, _) = mod2_gauss_elimination(A, b); if(!status) { puts("Impossible"); } else { printf("%d\n", cnt); } return 0; }