yukicoder No.184 たのしい排他的論理和(HARD)
考え方はあってたけどランクの実装でバグってた。
問題:No.184 たのしい排他的論理和(HARD) - yukicoder
解法:bit的な意味で線形独立なものの個数を考えれば良い。そのためにランクを計算することになるが,通常と比べてxor演算して0と1を入れ替えるだけなのでラク。上三角行列になるように実装することに注意(ソースで言うところのrを入れてなかったせいでバグってた)。
以下ソースコード
const int MAXN = 100100; ll A[MAXN]; ll pp(int num) { ll ret = 1; for (int i = 0; i < num; i++) ret *= 2; return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N; i++) { cin >> A[i]; } // 行列のランクのようなものを計算する int r = 0; for (int i = 0; i < 64; i++) { // i個目のビットが1になっているものを探す int j = r; for (; j < N; j++) { if ((A[j]>>i)&1) break; } if (j != N) { swap(A[j], A[r]); // i個目のビットが1になっているものにxorをかける for (int k = r+1; k < N; k++) { if ((A[k]>>i)&1) A[k] ^= A[r]; } r++; } } int ans = 0; for (int i = 0; i < N; i++) { if (A[i]) ans++; } cout << pp(ans) << endl; return 0; }