結果
問題 | No.184 たのしい排他的論理和(HARD) |
ユーザー |
|
提出日時 | 2022-12-25 05:01:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 5,000 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 2,211 ms |
コンパイル使用メモリ | 200,356 KB |
最終ジャッジ日時 | 2025-02-09 20:41:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/184" #include <bits/stdc++.h> using namespace std; template <typename T> struct BinaryBasis{ vector<T> basis, original; BinaryBasis(const vector<T>& vec){ for(auto x : vec){ T y = x; for(auto z : basis){ y = min(y, y ^ z); } if(y > 0){ basis.push_back(y); original.push_back(x); } } normalize(); } void add(const T &x){ T y = x; for(auto z : basis){ y = min(y, y ^ z); } if(y > 0){ basis.push_back(y); original.push_back(x); } } void normalize(){ sort(basis.begin(), basis.end()); for(int i = 0; i < (int) basis.size(); ++i){ for(int j = 0; j < i; ++j){ basis[i] = min(basis[i], basis[i] ^ basis[j]); } } } bool exist(const T &x){ T y = x; for(auto z : basis){ y = min(y, y ^ z); } return y > 0; } T kth_element(const long long &k){ T res = 0; for(int i = 0; i < (int) basis.size(); ++i){ if(k & (1LL << i)){ res ^= basis[i]; } } return res; } size_t size(){ return basis.size(); } }; int main(){ int n; cin >> n; vector<long long> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; } BinaryBasis<long long> basis(a); cout << (1LL << (basis.size())) << "\n"; }