Good Bye 2022 : F. Koxia and Sequence

ようやくだ…。
https://codeforces.com/contest/1770/problem/F

問題

非負整数N,X,Yが与えられる。
N要素の非負整数列Aのうち、

• 全要素の和がX
• 全要素のbitwise-orがY

となるものに対し、全要素のxorにおける全数列のxorを求めよ。

解法

各要素において、有効な数列のうち各値が登場する頻度は等しい。
よってNが偶数の時は解は0。
以下Nは奇数とする。

A[0]=tとなるケースが奇数回かどうかを考える。
とはいえtを総当たりするのは大変なので、2進数の桁ごとに考える。

各要素のxorは、Yをbitsetとみなしたときのsubsetである。
よってそのsubsetを総当たりし、Lucasの定理の要領で条件を満たす数列の組み合わせの偶奇を求めて行こう。

ll N,X,Y;

int ok(ll a,ll b) {
	if(a<0||b<0) return 0;
	return (a&b)==a;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	if(N%2==0) {
		cout<<0<<endl;
		return;
	}
	
	ll ret=0;
	for(int sm=Y;sm>0;sm=(sm-1)&Y) {
		FOR(i,20) if(sm&(1<<i)&&ok(X-(1<<i),N*sm-(1<<i))) ret^=1<<i;
	}
	
	cout<<ret<<endl;
	
}

まとめ

ようやく2022年が終わる…。