Codeforces #242 Div2 C. Magic Formulas

CF242は不参加のため練習のみ。Eにだいぶ苦戦した。
http://codeforces.com/contest/424/problem/C

問題

N要素の配列P[i]に対し、配列のindexを1-indexとすると、Q[i]は次のように定義される。
Q[i] = P[i] ^ (1 % i) ^ (2 % i) ^ ... (N % i)

Q[i]の全要素のxorを答えよ。

解法

xorは交換法則が成り立つので、結局行うべきは
P[1] ^ P[2] ^ ... ^ P[N] ^ (1 % 1) ^ (2 % 1) ^ ... (N % 1) ^ (1 % 2) ^ (2 % 2) ^ ... (N % 2) ^ (1 % N) ^ (2 % N) ^ ... (N % N)
である。
最初のP[i]のxorはO(N)で出来るので問題ない。
問題はその後のN^2個である。

同じmodを取る項 (1 % i) ^ (2 % i) ^ ... (N % i) を高速に計算することを考える。
(1 % i) ～ (2i % i)のxorを取れば、同じ値が２回ずつ出てくるので全体のxorは0になることがわかる。
よってN/(2*i)*(2*i)までの部分は0になる。
残り(N/(2*i)*(2*i)+1)%i ～N%iの部分は結局1 ^ 2 ^ ... ^ N%(2*i)%i になるので、事前に1～iの累積xorを計算しておけばO(1)で求められる。

よって全体でO(N)で計算可能。

int N;
ll tot[1000001];
void solve() {
	int f,i,j,k,l,x,y;
	
	ll ret=0;
	FOR(i,1000000) tot[i+1]=tot[i]^(i+1);
	
	cin>>N;
	FOR(i,N) cin>>x, ret ^= x;
	FOR(i,N) {
		y = N%(2*(i+1));
		if(y>=i+1) ret ^= tot[i]^tot[y-(i+1)];
		else ret ^= tot[y];
	}
	cout << ret << endl;
}

問題

あまりP[i]の意味ないなこれ。CFは時々こういう問題が出てくる。