Codeforces #785 : Div2 E. Power or XOR?

時間ギリギリで解いてるな。
https://codeforces.com/contest/1673/problem/E

問題

2の累乗からなる整数列Bが与えられる。
B[0]＾B[1]＾B[2]＾・・・・という値を考えたとき、演算子「＾」のうちK個以上がbitwise-xorで、それ以外が累乗を意味するものとする。
全パターンのxorを取ったとき、2進数表記で下2^20桁を答えよ。

解法

Bの各値は2以上なので、累乗がいくつか続くとその値はすぐ2^(2^20)を超える。
よって、ある累乗演算子が連続した区間の値を求め、Lucasの定理で他の部分の演算子の決め方の総数の偶奇を求めて奇数になる分について、解に計上していこう。

int N,K;
int B[1<<20];

ll sum[25][3];
int dp[1<<20];
int lucas(ll N,ll K) { // C(N,K)の偶奇
	if(K<0 || K>N) return 0;
	return ((~N)&K)==0;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	cin>>N>>K;
	FOR(i,25) {
		FOR(k,3) {
			FOR(j,1<<20) if(j+k>=K) {
				if(j<=N-1-i-k&&lucas(N-1-i-k,j)) sum[i][k]^=1;
			}
		}
	}
	
	FOR(i,N) cin>>B[i];
	ll ret=0;
	FOR(i,N) {
		ll a=B[i];
		if(sum[0][(i!=0)+(i<N-1)]) {
			dp[a]^=1;
		}
		for(j=1;i+j<N;j++) {
			if(B[i+j]>=20) break;
			a*=1<<B[i+j];
			if(a>=1<<20) break;
			if(sum[j][(i!=0)+(i+j<N-1)]) {
				dp[a]^=1;
			}
		}
		
	}
	s.resize(1<<20,'0');
	FOR(i,1<<20) if(dp[i]) s[i]='1';
	while(s.size()&&s.back()=='0') s.pop_back();
	reverse(ALL(s));
	
	if(s.empty()) {
		cout<<0<<endl;
	}
	else {
		cout<<s<<endl;
	}
	
	
}

まとめ

言語によってこの演算子違ってややこしいよね。