yukicoder : No.983 Convolution

この回解き切ってないものもあるけど終わったのから書いていくか。
https://yukicoder.me/problems/no/983

問題

整数列Aが与えられる。
一部の項目は任意の整数を設定できるものとする。
B[k] = sum(A[i] × A[j]) (ただしi and j = k)
とする。Aの値を最適に設定したとき、Bの全要素のGCDの最大値を求めよ。

解法

包除原理を考えると、pをbitmask表記でkを含むN未満の整数全部、qをbitmask表記でkを含むN未満の整数全部からkを除いたものとして、
B[k] = sum(A[p])^2 - sum(B[q])
としてkを大きい順に求めることができる。
sum(A[p])を高速ゼータ変換で求めたうえ、後半の除算をメビウス演算で求めればいずれもO(NlogN)で求められる。

その後Bの全要素のGCDを取ればよい。
…この演算、結局Bの各要素はAの各要素の2乗になるらしい。
そのためAの未確定要素は0にしておいて差支えない。

int N;
ll A[1<<18];
__int128 B[1<<18];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]==-1) A[i]=0;
	}
	
	FOR(i,18) FOR(j,1<<18) if((j&(1<<i))==0) A[j]+=A[j^(1<<i)];
	
	FOR(i,1<<18) {
		B[i]=A[i];
		B[i]*=B[i];
	}
	
	FOR(i,18) FOR(j,1<<18) if((j&(1<<i))==0) B[j]-=B[j^(1<<i)];
	__int128 T=0;
	FOR(i,1<<18) T=__gcd(T,B[i]);
	if(T==0) T=-1;
	cout<<(ll)T<<endl;
}

まとめ

頑張って高速ゼータ変換とかしたのにな。