(cache)AtCoder Grand Contest 034 F - RNG and XOR

お気持ち議論で解けた（気分になった）ので共有

元凶

rsm9.hatenablog.com

？？？「OR版がゼータ変換で解けるならXOR版もWHTで同じように解けるのでは？」

立式

まず0がiになるまでの期待値はiが0になるまでの期待値と同じなのでそっちを求める。（天才的言い換え）

求める期待値を $h_{0}, h_{1}, \dots, h_{2^{N} - 1}$ とする

$g_{j} = \frac{a_{j}}{\sum_{i} a_{i}}$ とする

$1 \leq i$ について $h_{i} = \sum_{j = 0}^{2^{N} - 1} g_{j} (h_{i \oplus j} + 1)$

$S = \sum_{i = 0}^{2^{N} - 1} h_{i}$ とすると

$S - h_{0}$

$= \sum_{i = 1}^{2^{N} - 1} h_{i}$

$= \sum_{i = 1}^{2^{N} - 1} \sum_{j = 0}^{2^{N} - 1} g_{j} (h_{i \oplus j} + 1)$

$= \sum_{j = 0}^{2^{N} - 1} g_{j} \sum_{i = 1}^{2^{N} - 1} (h_{i \oplus j} + 1)$

$= \sum_{j = 0}^{2^{N} - 1} g_{j} (S - h_{j} + 2^{N} - 1)$

$= S - \sum_{j = 0}^{2^{N} - 1} g_{j} h_{j} + (2^{N} - 1)$

したがって $h_{0} = \sum_{j = 0}^{2^{N} - 1} g_{j} h_{j} - (2^{N} - 1)$

ここで、長さ $2^{N}$ の列 $e = (1, 1, \dots, 1)$ を考えると

$h = c o n v (g, h + e) - 2^{N}$

となる。

$h_{0}$ に対応する式を線形結合から作ったので、ランク（のようなもの）が1足りないことに注意

Walsh-Hadamard Transforms

$h = c o n v (g, h + e) - 2^{N}$ の両辺をアダマール変換すると

$0 \leq i < 2^{N}$ について、 $w h t (h)_{i} = w h t (g)_{i} \times (w h t (h) + w h t (e))_{i} - 2^{N}$

ここで $w h t (e)_{i}$ は $i = 0$ で $2^{N}$ 、 $i \neq 0$ で $0$ である。

$i \neq 0$ のとき

$w h t (h)_{i} = w h t (g)_{i} \times w h t (h)_{i} - 2^{N}$

$w h t (g)_{i} \times w h t (h)_{i} - w h t (h)_{i} = 2^{N}$

$w h t (h)_{i} = \frac{2^{N}}{w h t (g)_{i} - 1}$

$w h t (g)_{i} \neq 1$ であることに注意

$i = 0$ のとき

$w h t (h)_{0} = w h t (g)_{0} \times w h t (h)_{0}$

ここで、 $w h t (g)_{0} = 1$ であるから、 $w h t (h)_{0}$ がどんな値でも条件を満たす

（この部分はランクが足りないことが原因だと考えられる）

一方で、 $h_{0} = 0$ であるから、 $\sum_{i = 0}^{2^{N} - 1} w h t (h)_{i} = 2^{N} \times h_{0} = 0$ より、 $w h t (h)_{0} = - \sum_{i = 1}^{2^{N} - 1} w h t (h)_{i}$

以上より、 $w h t (h)$ のすべての項が求まったので、 $h = i w h t (w h t (h))$ を計算すればよい

提出

atcoder.jp

beet's soil

競プロのことなど

AtCoder Grand Contest 034 F - RNG and XOR

元凶

立式

Walsh-Hadamard Transforms

$i \neq 0$ のとき

$i = 0$ のとき

提出

元凶

立式

Walsh-Hadamard Transforms

i≠0 のとき

i=0 のとき

提出

$i \neq 0$ のとき

$i = 0$ のとき