SRM697D1Med XorOrderDiv1
方針がダメだった
問題概要(原文)
$2^{M}$ 日間試合をする．チームは $N$ チームあり， $j$ 番目のチームの強さは $A_{j} (0 \leq A_{j} < 2^{M})$ であり，これは互いに相異なる．
0-indexedで $i$ 日目の試合では， チーム $j$ は $A_{j} \oplus i$ 点のペナルティをもらう． ペナルティが自分より小さいチームが $k$ チームあったとき， $f(k)$ 点加算される． $f(k):=k^2$ である．
$2^{M}$ 日後のチームの得点を $10^{9}+7$ で割ったあまりをそれぞれ求め， XORを取った値を求めよ．
考察
チーム $j$ の得点をそれぞれ求めることを考える．
$2^M$ が小さいとき，それぞれの日について，ペナルティを計算して得点を求めることができる．しかし， $2^M$ は大きくなりうるのでこのような方針は取れない． ここで， $x$ 番目のビットがフリップされることにより， チーム $j$ の勝ち負けが変化するチームの数を $B(j,x)$ とする．これはそれぞれにビットについてのみ計算すればよく，一つのビットあたり $O(logN)$ 程度でできる．
これで，ビットのフリップによるペナルティの変動ではなくて，ビットのフリップによる順位の変動がわかるようになった．
さて，チーム $j$ の得点を求めよう． 簡単のため，得点関数 $f(k):=k$ としたものをまず考える．これはつまり， チーム $j$ が取った順位を全て足した値を求めよ，ということである． ここで，$[0,2^{M})$ からランダムに数を $1$ つ選んだときの順位の期待値に $2^M$ をかけた値と，先ほどの値は等しい．
$\sum_{k = 0}{2^{M - 1}} f(k) = 2^{M} \sum_{k = 0}{2^{M - 1}} p(i)i$ という式を考える，$p(i)$ は $i$ 位を取る確率である．今 $p(i) = 2^{-M}$ を考えているので，これは恒等式となる．
ここで， $x$ 個のビットについて処理したときのチーム $j$ の順位の期待値を $E(j,x)$ とする． $E(j,x)$ は以下のように表せる．
\[ E(j,x) = \begin{cases} 0 & (x = 0)\\ \frac{1}{2}E(j,x-1) + \frac{1}{2}(E(j,x-1) + B(j,x-1)) & (\text{otherwise}) \end{cases} \]
この問題であれば動的計画法を用いて， $O(NM)$ で解ける．
では $f(k):=k^2$ について解くことを考えよう． $F(j,x)$ を $x$ 個のビットについて処理したときのチーム $j$ の 得点とする． $P(j,x,i)$ を $x$ 個のビットについて処理したとき，チーム $j$ が $i$ 位となる確率，とする． $F(j,x)$ は以下のように表せる．
\[ \begin{aligned} F(j,x) & = \sum P(j,x,i)i^2\\ & = \frac{1}{2}\sum P(j,x-1,i)i^2 + \frac{1}{2}\sum P(j,x-1,i) (i+B(j,x-1))^2\\ & = \sum P(j,x-1,i)i^2 + B(j,x-1)\sum P(j,x - 1,i)i + \frac{1}{2}B(j,x-1)^2 \sum P(j,x-1,i)\\ & = F(j, x-1) + B(j,x-1)E(j,x-1) + \frac{1}{2}B(j,x-1)^2\\ & = \begin{cases} 0 & ( x = 0)\\ F(j, x-1) + B(j,x-1)E(j,x-1) + \frac{1}{2}B(j,x-1)^2 & (\text{otherwise}) \end{cases} \end{aligned} \]
この問題でも動的計画法を用いて $O(NM)$ で解ける． 計算量としては，$B(j,x)$ を求める部分が最も重く $O(NMlogN)$ である．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class XorOrderDiv1
{
public int get(int m, int n, int a0, int b)
{
var X = 1 << m;
var A = new long[n];
for (long i = 0; i < n; i++)
A[i] = (a0 + i * b) % X;
Array.Sort(A);
return f(A, m);
}
int f(long[] A, int m)
{
var n = A.Length;
var ans = 0L;
const long MOD = (long)1e9 + 7;
const long INV2 = 500000004;
foreach (var x in A)
{
var b = new List<long>();
for (int i = 0; i < m; i++)
{
var y = ((x >> i) ^ 1) << i;
var z = y;
for (int j = 0; j < i; j++)
z |= 1L << j;
z++;
var p = Array.BinarySearch(A, y);
var q = Array.BinarySearch(A, z);
if (p < 0) p = ~p;
if (q < 0) q = ~q;
b.Add(q - p);
}
long e = 0;
long f = 0;
foreach (var k in b)
{
var ne = e + INV2 * k;
ne %= MOD;
var nf = f + k * e + INV2 * ((k * k) % MOD);
nf %= MOD;
e = ne;
f = nf;
}
f *= 1 << m;
f %= MOD;
ans ^= f;
//Debug.WriteLine(x); Debug.WriteLine(b.AsJoinedString());
}
return (int)ans;
}
}
コメント
- 式変形が大事
