Codeforces #750 Div2 : F2. Korney Korneevich and XOR (hard version)

Div2のF問題にしては易しめ？
https://codeforces.com/contest/1582/problem/F2

問題

整数列Aが与えられる。
Aの部分列のうち昇順であるものに対しxorを取ったとき、構成できる値を列挙せよ。

解法

f(n,x,a) := Aのn項目まで見たとき、xorの値がxであって、次に来る値がaである(末尾がa-1以下である)かどうか

とする。
f(n,x,A[n])=1である場合、f(n+1,x^A[n],b)=1 (b＞A[n])とできる。
インラインDPの要領でf(n,x,a)のテーブルを埋めて行こう。
f(n,x,a)=1ならf(n,x,a+1)も1なことを利用し、同じテーブルを何度も更新することを避けられる。

int N;
int A[5050];
int bm[5050][8192];
int can[5050][8192];
vector<int> cand[5050];

void add(int num,int val) {
	can[num][val]=1;
	int i;
	for(i=num+2;i<=5005;i++) {
		if(bm[i][val]) break;
		bm[i][val]=1;
		cand[i].push_back(val);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	add(0,0);
	
	FOR(i,N) {
		cin>>x;
		FORR(c,cand[x+1]) add(x,x^c);
		cand[x+1].clear();
	}
	vector<int> ret;
	FOR(i,8192) if(bm[5003][i]) ret.push_back(i);
	cout<<ret.size()<<endl;
	FORR(c,ret) cout<<c<<" ";
	cout<<endl;
	
}

まとめ

D問題ぐらいでも良い気はする。