AtCoder ARC #137 : D - Prefix XORs

最近FPSと高速ゼータ変換ネタなんか多いな。
https://atcoder.jp/contests/arc137/tasks/arc137_d

問題

N要素の整数列Aが与えられる。
以下の手順をK回行ったとき、(1-originの場合で)Aの末尾の要素A[N]はどうなるか。

• A[i]を、A[1]...A[i]のxorで置き換える。この処理は全要素同時に行う。

K=1～Mそれぞれのケースに対し答えよ。

解法

A[N-i]=1の場合を考え、A[N-i]がA[N-1]に寄与するケースを実験などで求めると、Binom(i+K-1,K-1)の偶奇で決まることがわかる。
Lucasの定理より、Binom(i+K-1,K-1)が奇数となるのは、(i+K-1)の2進数表記で立っているbitが、(K-1)の2進数表記で立っているbitをすべて包含するケースである。
言い換えると、iと(K-1)で共通するbitを持たないことであり、~iに(K-1)が包含されるケースといえる。

ここまでくると高速ゼータ変換に持ち込める。
S=max(N,M)とし、B[S-1-i]=A[N-1]で初期化し、Bに対し高速ゼータ変換を適用しよう。
あとはB[K-1]を答えればよい。

ll B[1<<22];
int N,M,S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	S=1;
	while(S<max(N,M)) S*=2;
	FOR(i,N) {
		cin>>x;
		B[S-1-(N-1-i)]=x;
	}
	for(x=1;x<=S;x*=2) {
		FOR(j,S) if(j&x) B[j^x]^=B[j];
	}
	FOR(j,M) cout<<B[j]<<" ";
	cout<<endl;
}

まとめ

二項係数周りの足しこみを高速ゼータ変換で行うの初めて見たな…。