TopCoder SRM 697 Div1 Medium XorOrderDiv1、Div2 Hard XorOrderDiv2

数字が合うまでだいぶ手間取ったけど解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14354
https://community.topcoder.com/stat?c=problem_statement&pm=14370

問題

N人の選手が2^M回試合を行う。
各人の選手の能力の初期値をA[i]とする。(A[i]は互いに異なる)。
i番目の選手のj日目の能力はA[i]^jとなる。
各日各選手は能力に応じて順位づけがなされ、ペナルティポイントが加算される。
ペナルティポイントは0-indexで能力降順に順位を付けたとき、x位ならx^2のポイントが付く。

Div2では2^M回の試合後の各人のペナルティポイントを列挙せよ。
Div1では、2^M回の試合後の各人のペナルティポイントのxorを取った値を答えよ。

解法

Div1にしろDiv2にしろ、各人のペナルティポイントを具体的に計算してしまおう。

2^M回試合をするということは、A[i]を２進数表記でM桁だと考えると、各桁の値が反転することが2^(M-1)回ずつあることになる。
よって、他のどんな相手に対しても2^(M-1)回は勝利し、2^(M-1)回は敗北する。

問題は、ペナルティポイントは順位の２乗に対して付くため、上記の敗北回数を足し合わせても求める答えは得られない。
そこで、負ける回数の１乗和と２乗和を管理しよう。

d桁目より上が同じで、i桁目が異なる相手がa人いた場合、2^M回の試合中2^(M-1)回で順位がa落ちる。
(この負け回数aはEditorialによるとtrieを構築して求めているが、自分は最初にA[i]をソートしてそれをlower_boundで二分探索して求めた)
dを下の位から順に見ていって、その際の負ける回数の１乗和と２乗和をそれぞれ加算すればよい。

ll A[202020];
ll mo=1000000007;

class XorOrderDiv1 {
	public:
	pair<ll,ll> dfs(int cur,int L,int R,int d,int X,int Y) {
		if(d<0) return {0,0};
		int X2 = (X+Y)/2;
		int M = lower_bound(A+L,A+R,X2)-A;
		
		pair<ll,ll> r;
		ll num;
		if(cur<X2) {
			num = R-M;
			r = dfs(cur,L,M,d-1,X,X2);
		}
		else {
			num = M-L;
			r = dfs(cur,M,R,d-1,X2,Y);
		}
		r.second = (2*r.second + 2*num*r.first +  ((num*num%mo)<<(d)))%mo;
		r.first = (2*r.first + (num<<(d)))%mo;
		return r;
	}
	
	int get(int m, int n, int a0, int b) {
		int i;
		FOR(i,n) A[i] = (a0 + 1LL*i*b) & ((1<<m)-1);
		sort(A,A+n);
		
		ll ret=0;
		FOR(i,n) ret ^= dfs(A[i],0,n,m-1,0,1<<m).second;
		return ret;
	}
}

まとめ

こういう桁DP、Codeforcesのイメージ。