結果
問題 | No.2672 Subset Xor Sum |
ユーザー |
![]() |
提出日時 | 2024-03-19 15:04:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 908 bytes |
コンパイル時間 | 1,771 ms |
コンパイル使用メモリ | 196,068 KB |
最終ジャッジ日時 | 2025-02-20 07:40:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 66 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); //XORの総和が0でないならNo //鳩ノ巣原理より、N>=5001ならYes int N, M=8192, S=0; cin >> N; vector<int> A(N); for (int i=0; i<N; i++){ cin >> A[i]; S ^= A[i]; } if (S != 0){ cout << "No" << endl; return 0; } if (N >= 5001){ cout << "Yes" << endl; return 0; } //dp(i): iを作る方法の総数 //dp(0) >= 3ならばYes vector<int> dp(M); dp[0] = 1; for (int i=0; i<N; i++){ vector<int> pd(M); for (int j=0; j<M; j++){ pd[j] = min(3, pd[j]+dp[j]); pd[j^A[i]] = min(3, pd[j^A[i]]+dp[j]); } swap(dp, pd); } cout << (dp[0] == 3 ? "Yes" : "No") << endl; return 0; }