yukicoder : No.1503 Bitwise And Convolution Twisted

色々ガチャガチャやってると通ってしまいそう。
https://yukicoder.me/problems/no/1503

問題

2^N要素の整数列A,Bが与えられる。
で定義される数列Cを求めよ。

解法

高速ゼータ変換や高速メビウス変換を駆使すればよさそうというのは何となくわかる。
詳細な理由はEditorialを参照頂くとして、Aを高速ゼータ変換した数列A'と、Bを高速メビウス変換した数列B'のアダマール積を取り、再度高速ゼータ変換をするとよい。

int N,M;
ll A[1<<20],B[1<<20],C[1<<20];
const ll mo=998244353;

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

まとめ

うーん、ここら辺アダマール積や高速ゼータ変換の知識がないと自力で式変換できないな。