AtCoder ABC #367 : G - Sum of (XOR^K or 0)

これは厳しい。
https://atcoder.jp/contests/abc367/tasks/abc367_g

問題

N要素の整数列Aが与えられる。
Aの各値は2^L(L=20)未満の整数である。

Aの部分列のうち、要素数がMの倍数のものについて、xorを取った値のK乗の総和を求めよ。

解法

C[i] := xorと取った値がiとなるようなAの部分列のうちMの倍数の要素数のものの個数
とし、C[i]を求めよう。

2^L要素の多項式列を考える。
A[i]に対応し、A[i]番目の要素がx、0番目の要素が1となるN個の列を考えよう。
これらをxorで畳み込んだ時、i番目の要素についてx^nMの係数の総和がC[i]となる。

また、各多項式をmod (1-x^M)を取りながら計算すれば、定数項だけ取ればよくなる。

元のN個の列をそれぞれアマダール変換すると、各項目は1+xか1-xとなる。
これらをN個分畳み込んで、また最後に戻そう。

int N,M,K;
const int L=20;
int A[202020];
const ll mo=998244353;

ll F[202020][101];
ll G[202020][101];
ll FG[202020];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

vector<ll> DWTxor(vector<ll> v) {
	int n=v.size(),i,j,m,b;
	for(b=1;b<n;b*=2) {
		for(i=0;i<n;i+=2*b) FOR(j,b) {
			ll x=v[i+j],y=v[i+j+b];
			v[i+j]=(x+y)%mo;
			v[i+j+b]=(x-y+mo)%mo;
		}
	}
	return v;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	F[0][0]=G[0][0]=1;
	FOR(i,N) {
		FOR(j,M) {
			F[i+1][j]=(F[i][j]+F[i][(j+M-1)%M])%mo;
			G[i+1][j]=(G[i][j]-G[i][(j+M-1)%M]+mo)%mo;
		}
	}
	//FGの積
	FOR(i,N+1) {
		FOR(j,M) (FG[i]+=F[i][j]*G[N-i][(M-j)%M])%=mo;
	}
	
	vector<ll> A(1<<L),C(1<<L);
	FOR(i,N) {
		cin>>x;
		A[x]++;
	}
	A=DWTxor(A);
	FOR(i,1<<L) {
		A[i]%=mo;
		C[i]=FG[(A[i]+N)%mo/2];
	}
	C=DWTxor(C);
	
	ll ret=0;
	FOR(i,1<<L) {
		(ret+=C[i]*modpow(i,K))%=mo;
	}
	ret=ret*modpow(1<<L)%mo;
	cout<<ret<<endl;
	
	
	
}

まとめ

こんなの自力で思いつける気がしないな。
他にいい導出法あるのかな。