Codeforces #812 : Div2 F. Lost Array

コードがかなり短くて済む。
https://codeforces.com/contest/1713/problem/F

問題

(N+1)*(N+1)の2次元配列Bを考える。
B[0][x]=0で、B[y][0]が与えられているとする。
正整数x,yに対しB[y][x]=B[y-1][x] xor B[y][x-1]とする。B[*][N-1]をそれぞれ答えよ。

解法

B[0][x]がB[*][N-1]に影響するかどうかは、Lucasの定理の要領で求められる。
高速ゼータ変換の要領で、B[*][N-1]に影響する要素のxorを高速に求めることができる。

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

まとめ

Lucasから高速ゼータ変換につなげると、言われてみればよくありそうだけど、あんまり遭遇した記憶ないな。