数字が合うまでだいぶ手間取ったけど解けて良かった。
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]を2進数表記でM桁だと考えると、各桁の値が反転することが2^(M-1)回ずつあることになる。
よって、他のどんな相手に対しても2^(M-1)回は勝利し、2^(M-1)回は敗北する。
問題は、ペナルティポイントは順位の2乗に対して付くため、上記の敗北回数を足し合わせても求める答えは得られない。
そこで、負ける回数の1乗和と2乗和を管理しよう。
d桁目より上が同じで、i桁目が異なる相手がa人いた場合、2^M回の試合中2^(M-1)回で順位がa落ちる。
(この負け回数aはEditorialによるとtrieを構築して求めているが、自分は最初にA[i]をソートしてそれをlower_boundで二分探索して求めた)
dを下の位から順に見ていって、その際の負ける回数の1乗和と2乗和をそれぞれ加算すればよい。
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のイメージ。