AtCoder ARC #205 : E - Subset Product Problem

うーむもったいない。
https://atcoder.jp/contests/arc205/tasks/arc205_e

問題

N要素の整数列Aが与えられる。
Aの各要素は0以上10^6以下である。

A[i]に対し、j≦iかつA[j] & A[i] = A[j]となるjの積を求めよ。

解法

Aは2進数で20桁以下なので、上位10bitと下位bitで分けて考える。
f(n, H, L) := A[0]～A[n]のうち、上位10bitがHで、下位10bitをL'としたときL' | L = L'となるものの積

求める値は、A[n]の上位10bitをX、下位10bitをYとすると、f(n, X', Y) (X'はX' & X = X' となるもの)の積である。
また、f(n-1,H,L)とf(n,H,L)については、H=Xの場合のみin-placeで更新すればよい。

こうするとテーブルの更新と、テーブルの参照がいずれも2^10通り行えばよく、間に合う。

int N;
int A[404040];
const ll mo=998244353;
ll dp[1<<10][1<<10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1<<10) FOR(j,1<<10) dp[i][j]=1;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>A[i];
		x=A[i]>>10;
		y=A[i]%(1<<10);
		
		int mask=0;
		ll ret=1;
		FOR(mask,1<<10) if((mask|y)==mask) (dp[x][mask]*=A[i])%=mo;
		FOR(mask,1<<10) if((mask|x)==x) (ret*=dp[mask][y])%=mo;
		cout<<ret<<endl;
		
	}
	
	
}

まとめ

無駄に高速ゼータ変換をしようとしてしまい、TLE連発してしまった。