結果
| 問題 |
No.2672 Subset Xor Sum
|
| コンテスト | |
| ユーザー |
 Astral__
|
| 提出日時 | 2024-03-15 21:41:38 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 204 ms / 2,000 ms |
| コード長 | 13,145 bytes |
| コンパイル時間 | 3,143 ms |
| コンパイル使用メモリ | 252,056 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-09-30 04:16:07 |
| 合計ジャッジ時間 | 6,380 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 66 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//using uLL = unsigned __int128;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using pq = priority_queue<T>;
using pll = pair<long long, long long>;
using pii = pair<int, int>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvc = vector<vector<vector<char>>>;
using vvvd = vector<vector<vector<double>>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvp = vector<vector<pair<ll, ll>>>;
using vvb = vector<vector<bool>>;
using vvd = vector<vector<double>>;
using vp = vector<pair<ll, ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vu = vector<unsigned long long>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
#define vvvm vector<vector<vector<mint>>>
#define vvm vector<vector<mint>>
#define vm vector<mint>
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;
template <typename T1, typename T2>
using uset = unordered_set<T1, T2>;
#define rrr(l, r) mt()%(r-l+1)+l
#define rep(i, s, f) for(long long i = s; i <= f; i++)
#define rep1(i, s, f) for(long long i = s; i <= f; i++)
#define per(i, s, f) for(long long i = s; i >= f; i--)
#define per1(i, s, f) for(long long i = s; i >= f; i--)
#define all0(x) (x).begin() ,(x).end()
#define all(x) (x).begin() + 1, (x).end()
#define ENDL '\n'
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//これが本当の組み込み関数ってね（笑）
template <typename T>
int LB(vector<T> &A, T x) {
return lower_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
int UB(vector<T> &A, T x) {
return upper_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
void UNIQUE(vector<T> &A, int indexed) {
sort(A.begin() + indexed, A.end());
A.erase(unique(A.begin() + indexed, A.end()), A.end());
}
int msb(long long a) {
if(a == 0) return -1;
return 64 - int(__builtin_clzll(a));
}
template<typename T = long long>
void chmin(T &a, T b) {
a = min(a, b);
}
template<typename T = long long>
void chmax(T &a, T b) {
a = max(a, b);
}
//////////////////////////////////////////////////////////////////////
//数学系
///////////////////////////////////////////////////////////////////////
ll extgcd (ll a, ll b, ll &x, ll &y) {
if(b == 0) { x = 1;y = 0;return a;}
ll d = extgcd(b, a%b, y, x);
y -= a/b * x;
return d;
}
template <typename T>
T ceil__(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;
else return a / b;
}
template <typename T>
T floor__(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;
else return a/b - 1;
}
ll modpow(ll x, ll y, ll mod) {
if(x > mod) x %= mod;
if(y == 0) return 1;
ll res = modpow(x, y >> 1, mod);
res = res * res % mod;
if(y & 1) res *= x, res %= mod;
return res;
}
ll sqrt__(ll a) {
ll l = 0;
ll r = 3037000499LL;
while(l < r) {
ll mid = (l + r + 1) / 2;
if(mid * mid <= a) l = mid;
else r = mid - 1;
}
return l;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//グローバル変数を置くところ
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize "trapv" //お祈り。変数同士の演算でのみ感知。代入や、 a *= 10000 では感知しない。
const ll big = 1001001001;
const ll BIG = 1001001001001001001LL;
const double pi = 3.141592653589793;
vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; // 座標平面において、(番兵) → ↓ ← ↑ ※ 右から時計回り 注 : グリッド or 座標で上下は反転する。
vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1};
//const ll mod = 1000000007;
//const ll mod = 998244353;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename X = unsigned long long, typename S = unsigned long long>//X..直 S...個数
struct Binary_Trie_Tree {
struct Node {
Node* l = nullptr;
Node* r = nullptr;//値1、値2。左の子に対応するポインタと、右の子に対応するポインタ。
S s = 0; //値3。このNodeに対応するprefixを持つ要素の総数。
X lazy = 0; //値4。xorの遅延伝播のうち、このノードに止まっている分。
Node (){}
};
int W = 0;//論文中のWの定義と同様。insertする整数のうち、最大値のbit数
Node* root = new Node;//Binary_Trie_Treeの根を表すノード。
Binary_Trie_Tree(int _W) : W(_W){}//Wを指定する。
private:
void search_ie(Node* k, int l, S t, X& x) {//insert/eraseの探索関数。tは関数を共通化する為のパラメータ。t >= 1ならinsert、t <= -1ならerase
eval(k, l);
k -> s += t;
//assert(k -> s >= 0);
if(l == W) return;
//evalによって既に子の存在は保証されている。
if(x >> (W - l - 1) & 1) search_ie(k -> r, l+1, t, x);//右に移動 //Wbit中、上からl + 1番目 ⇔ 下から W - l番目
else search_ie(k -> l, l+1, t, x);//左に移動
return ;
}
S search_count(Node* k, int l, X& x) {//countの為の探索関数
eval(k, l);
if(l == W) return k -> s;//葉に到達したならばそのsを返す。
if(k -> s == 0) return S(0);//s = 0の頂点が存在したならば即座に0を返す。
//evalによって既に子の存在は保証されている。
if(x >> (W - l - 1) & 1) return search_count(k -> r, l+1, x);//右に移動
else return search_count(k -> l, l+1, x);//左に移動
}
X search_maix(Node *k, int l, int type) {//type == 1がmax、type == 0がmin
eval(k, l);
if(l == W) return X(0);//葉なら即座に0を返す。
if(type == 1) {
if(k -> r -> s != 0) return (X(1) << (W - l - 1)) + search_maix(k -> r, l+1, type); //右に移動 //上からl+1bit目が1だとわかった ⇔ 下からW - lbit目が1
else return search_maix(k -> l, l+1, type);//左に移動
}
else {
if(k -> l -> s != 0) return search_maix(k -> l, l+1, type);//左に移動
else return (1ULL << (W - l - 1)) + search_maix(k -> r, l+1, type);//右に移動
}
}
pair<X, S> search_kth(Node *k, int l, S& remain) {
eval(k, l);
if(l == W) return pair(X(0), k -> s);//葉なら即座に0を返す。
if(k -> l -> s >= remain) return search_kth(k -> l, l+1, remain);
else {
remain -= k -> l -> s;
auto f = search_kth(k -> r, l+1, remain);
f.first += (X(1) << (W - l - 1));//上からl+1bit目⇔したからW - lbit目
return f;
}
}
void eval(Node* k, int l) {
X x = k -> lazy;//今のノードのlazy
if(l != W) {//葉でないなら
if(k -> l == nullptr) k -> l = new Node;//左の子を作成
if(k -> r == nullptr) k -> r = new Node;//右の子を作成
k -> l -> lazy ^= x;//伝播
k -> r -> lazy ^= x;//伝播
}
//Wbit中、上からl+1番目 ⇔ 下から W - l番目
if(x >> (W - l - 1) & 1) swap(k -> l, k -> r);//相当するbitが立っているならswap
k -> lazy = 0;
return ;
}
S upper_bound_(Node* k, int l, X& x) {//x以下の要素の総数
eval(k, l);
if(l == W) return k -> s;
if(x >> (W-l-1)&1) return upper_bound_(k -> r, l+1, x) + k -> l -> s;
else return upper_bound_(k -> l, l+1, x);
}
public:
void insert(X x, S cnt = 1) {//値xをcnt個挿入
search_ie(root, 0, cnt, x);
}
void erase(X x, S cnt = 1) {//値xをcnt個削除(元の個数を超えた場合エラー)
search_ie(root, 0, -1ULL * cnt, x);
}
S count(X x) {//値xの個数
return search_count(root, 0, x);
}
X max_element() {//最大値 要素数 = 0の場合エラー
assert(root -> s > 0);
return search_maix(root, 0, 1);
}
X min_element() {//最小値 要素数 = 0の場合エラー
assert(root -> s > 0);
return search_maix(root, 0, 0);
}
pair<X, S> kth_element(S k) {//小さい方からk番目の値とその個数 要素数 < kの場合エラ-
assert(root -> s >= k);
return search_kth(root, 0, k);
}
void ope_xor(unsigned long long x) {//収容されている要素全てにxをxor作用させる
if(root -> s == 0) return;//要素が存在しない
root -> lazy ^= x;
eval(root, 0);
}
S upper_bound(X x) {//xより大きい最小の要素が何番目か
return 1 + upper_bound_(root, 0, x);
}
S lower_bound(X x) {//x以上の最小の要素が何番目か
if(x == 0) return size();
else return upper_bound(x - 1);
}
S size() {//収容されている要素の総数
return root -> s;
}
};
void solve() {
int N;
cin >> N;
vi A(N+1);
rep(i,1,N) cin >> A[i];
int x = 0;
rep(i,1,N) x ^= A[i];
if(x != 0) {
cout << "No" << endl;
return;
}
if(N > 5001) {
cout << "Yes" << endl;
return;
}
vb can(10000, false);
rep(i,2,N) {
vb pre(10000, false);
swap(pre, can);
can[A[i]] = true;
rep(j, 0, 9999) if(pre[j]){
can[j] = true;
int nw = j ^ A[i];
if(nw <= 9999) can[nw] = true;
}
}
if(can[0]) {
cout << "Yes" << endl;
return;
}
cout << "No" << endl;
return;
}
/*
-違法な読み替えをしていないか・違法な操作をしていないか
・実装が重そうな時は確認する 一度飛ばしても良い
・waが出た時は嘘を吐いていないかの他に、違法な操作をしていないかもチェックする
特にふわっとした操作は危ない
・区間をちょっと伸ばす←伸ばす余地はあるか
・選択肢のうち、どれでも良いから消す←本当にどれでも良いか 場合分けを挟んでないか
-その情報はdpで纏めて良いものか
・dpで持つ：「この先の探索をするのに必要な情報」 なぜ必要なのか？
・途中までは辻褄が合っても、最後に分岐とかはある
-何もわからないという時
・解を列挙した上で特徴づけ
・制約に具体的な数値が登場している←適当に解をいじると何となく性質が見えることが多い
・何もわからない（自由度が高い) という時
-解の形を貪欲で絞る
-上階が達成できガチ 必要条件をつみかさねていく ”非自明な最悪ケース（例：点の数が多いのに答え=0)”を作る時、何を意識したか？
・要素と制約をグラフで表してみる
・制約を「全ての要素についてoo ⇔ (1<=i<=N)で、iについてoo」といったように、独立なものに言い換えた方がやりやすいこともある
・よくわからないものを言い換える。
-慣れ親しんだ制約も、問題設定によってより扱いやすい形に言い換えられるかもしれない（例：グラフが連結)
-一つの解法で駄目な時、周辺の解法も試すようにする。周辺で見えないなら全部試す。
・「貪欲で最適解」と「解の形を絞って全探索」
・「dp/最適化」と「解の形を絞って全探索」と 上界を見積もる」
・「dp」と「必要な情報を言い換える・何でのその情報が必要なのか考える事による高速化」
・「dp」と「探索の順番を変更する: でかい方から、深い方から、DAGで先端になっている・或いは葉になっている所から、全てを逆に言い換えて時系列的に後ろから」
・「dp」と「軸にするものを変える: マスを軸にするのではなく、燃料を軸にするなど」
*/
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
ll T = 1;
//cin >> T;
rep(i, 1, T) {
solve();
}
return 0;
}