No.184 たのしい排他的論理和(HARD)
No.184 たのしい排他的論理和(HARD) - yukicoder
- uint64 を 64列 x N 行の mod 2 上の行列と考えて rank をもとめればよい。
- col = 63 にすべきところを col = 64 にしたりしてハマった。
// uint64_t 吐き出し法 std::vector<uint64_t> sweep_uint64(const std::vector<uint64_t> &A) { auto a = A; int n = a.size(); int row = 0; // O(64*N) for (int col = 63; col >= 0; --col) { int pivot = row; //row 行目以降だけ見る // 先頭から col 番目のビットが立っている a[i] を見つける while ( pivot < n && !(a[pivot] & 1ULL<<col) ) ++pivot; // col 番目にビットが立つ a はなかった if (pivot == n) continue; std::swap(a[row], a[pivot]); for (int i = row+1; i < n; ++i) { if ( a[i] & 1ULL<<col) a[i] ^= a[row]; } ++row; } return a; } using namespace std; class HappyXorHard { public: void solve(void) { int N; cin>>N; vector<uint64_t> A(N); REP(i,N) cin>>A[i]; A = sweep_uint64(A); int k = count_if(RANGE(A), [](uint64_t a) { return (a>0); }); cout<<(1LL<<k)<<endl; } };