Codeforces #409 Div1 D. Varying Kibibits

高速ゼータ変換系問題はDiv1Dというイメージがある。
http://codeforces.com/contest/800/problem/D

問題

整数列Lに対し整数f(L)は、各桁においてLの各要素の最大値を合わせたものとする。
(この定義だと、桁をそろえるためleading zeroを埋めても問題ない)

整数列Tが与えられる。Tに対し、関数G(x)を以下のように定める。

つまり、G(x)はTの部分集合Sのうちf(S)=xとなるものについて、Sの二乗和の総和を取ったものに最後xを掛けた値である。

G(0) xor G(1) xor ... G(999999)を答えよ。

解法

G'(x) = G(x)/x、すなわちG(x)の式の先頭のxを取り除いたものとする。
G'(x)の括弧内の値を具体的に各xについて求めてしまおう。

f(S)=xとなるSを直接求めるのは難しいので、f(S)≧xとなるケースについて考えることにする。
すなわち、H(x) := sum(G'(y)) (yの各桁は対応するxの桁の値以上である)を求めよう。
H(x)を求めてから包除原理の要領でG(x)を求める。

（CFが始まるのであとで埋める）

int N;
ll A[1010101],B[1010101],C[1010101],G[1010101];
ll p2[1010101];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	p2[0]=1;
	FOR(i,1010000) p2[i+1]=p2[i]*2%mo;
	
	FOR(i,N) {
		cin>>x;
		A[x]++;
		(C[x]+=1LL*x*x + B[x]*x)%=mo;
		(B[x]+=x)%=mo;
	}
	
	for(i=1;i<1000000;i*=10) {
		for(j=999999;j>=0;j--) if((j/i)%10!=9) {
			(A[j]+=A[i+j])%=mo;
			(C[j]+=C[i+j]+B[j]*B[i+j])%=mo;
			(B[j]+=B[i+j])%=mo;
		}
	}
	FOR(i,1000000) if(A[i]) G[i]=p2[A[i]-1]*C[i]%mo;
	for(i=1;i<1000000;i*=10) {
		FOR(j,1000000) if((j/i)%10!=9) {
			G[j]=(G[j]+mo-G[i+j])%mo;
		}
	}
	
	ll ret=0;
	FOR(i,1000000) ret ^= i*G[i];
	cout<<ret<<endl;
	
}

まとめ

高速ゼータ変換のテクをこういう風に使うの初めて見た。