AtCoder ABC #283 (ユニークビジョンプログラミングコンテスト2022 冬) : G - Partial Xor Enumeration

GもExも考察パートでミスっていてどうしようもない。
https://atcoder.jp/contests/abc283/tasks/abc283_g

問題

N個の非負整数が与えられる。
これらの部分集合のxorを取って得られる値を昇順に並べたとき、(重複を除いて)L番目～R番目のものを出力せよ。

解法

入力をN個のbit vectorとみなし、基底ベクトルを求めよう。
これを用いて、小さい順にx番目のものを求めよう。
基底ベクトルを(元の2進数表記の整数値で)小さい順に並べたものを数列B[i]とする。

求める値Vに、B[i]とのxorを取るかどうか、iの大きい順に判定する。
Vと(V[i] xor B[i])の大小は、B[0]～B[i-1]のxorを取るかどうか(2^i)通りをどう取ろうが変わらない。
これをもとに、x番目の値を特定するのにVと(V[i] xor B[i])どちらを選ぶか順にみて行けばよい。

int N;
ll L,R;
ll A[202020];

vector<ll> add(vector<ll> T,ll v) {
	FORR(t,T) v=min(v,t^v);
	if(v) T.push_back(v);
	//sort(ALL(T)); reverse(ALL(T));
	return T;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	vector<ll> V(N),W;
	FOR(i,N) {
		cin>>V[i];
		W=add(W,V[i]);
	}
	
	sort(ALL(W));
	for(ll v=L-1;v<R;v++) {
		ll c=v;
		ll cur=0;
		for(x=W.size()-1;x>=0;x--) {
			if((cur^W[x])>cur) {
				if(c>=1LL<<x) {
					c-=1LL<<x;
					cur^=W[x];
				}
			}
			else {
				if(c>=1LL<<x) {
					c-=1LL<<x;
				}
				else {
					cur^=W[x];
				}
			}
			
		}
		
		cout<<cur<<" ";
	}
	cout<<endl;
	
	
}

まとめ

最初基底ベクトル側をガチャガチャいじろうとして失敗。