Codeforces 1119H: Triple - hos.lyric's blog

https://codeforces.com/problemset/problem/1119/H

問題概要

$x, y, z$ が固定されている． $i = 1, \ldots, n$ に対して $a_i, b_i, c_i \in \{0, 1, \ldots, 2^k-1\}$ が与えられるので， $x T^{a_i} + y T^{b_i} + z T^{c_i}$ たちを $T$ の指数は XOR で畳み込む，というのを速くやる．

考察

Hadamard 変換すれば畳み込みが掛け算になる (常識) けど，そのままやると長さ $2^k$ の列を $n$ 個作らなければいけなくてダメ．

$x T^{a_i} + y T^{b_i} + z T^{c_i}$ を Hadamard 変換すると $v$ 項目は $(-1)^{\langle v, a_i \rangle} x + (-1)^{\langle v, b_i \rangle} y + (-1)^{\langle v, c_i \rangle} z$ になる ( $\langle , \rangle$ は $k$ ビットの整数を長さ $k$ のベクトルと見た内積) (定義)．ので，出てくる値は $\pm x \pm y \pm z$ しかない (これは定義に戻ることを忘れていても実験すればわかる)．ので， $v$ 項目の積は $(+ x + y + z)^{e_{000}} (- x + y - z)^{e_{100}} (+ x - y + z)^{e_{010}} \cdots$ みたいになって ( $e_{000}$ とかは $v$ に依存)， $x, y, z$ とか関係なくて $2^3$ 個の指数が上手く求まればうれしい．例えば $e_{000}$ は $\langle v, a_i \rangle, \langle v, b_i \rangle, \langle v, c_i \rangle$ が全部偶数になるような $i$ の個数とかそういう．手早く数えられそうでできない (「数える」という考えから抜けられなくてコンテスト中はここで止まった)．

「 $x, y, z$ とか関係なくて」とか言ったんだから特殊な値を代入して何かしてみるべき (極めて一般的な手法)．例えば $(x, y, z) = (1, 0, 0)$ として (これは自然な「特殊な値」)， $\prod_i (-1)^{\langle v, a_i \rangle} = (-1)^{e_{100}} (-1)^{e_{110}} (-1)^{e_{101}} (-1)^{e_{111}}$ だけど，これすら各 $v$ について手早くのは難しそうなうえに得られる情報量が少ない (普通の感想)．得られる情報量を多くしようとして指数の底を $0$ とか $\pm 1$ とかじゃないようにしても綺麗になる気配はない (たぶん普通の美的感覚)．ということで，代わりに $\sum_i (-1)^{\langle v, a_i \rangle} = + e_{000} - e_{100} + e_{010} - e_{110} + e_{001} - e_{101} + e_{011} - e_{111}$ を考えよう (これは，お気持ちはわからなくはないけど，かなり賢いと思う)．左辺は Hadamard 変換の線形性を使えるうれしい形をしていて， $\sum_i T^{a_i}$ を一度変換すれば各 $v$ について求まる．

同様に $\sum_i (-1)^{\langle v, b_i \rangle} = + e_{000} + e_{100} - e_{010} - e_{110} + e_{001} + e_{101} - e_{011} - e_{111}$ と $\sum_i (-1)^{\langle v, c_i \rangle} = + e_{000} + e_{100} + e_{010} + e_{110} - e_{001} - e_{101} - e_{011} - e_{111}$ が求まることがわかった．あとどんな関係があれば $e_{000}$ とかを特定できるか？というと，長さ $2^3$ の Hadamard 変換っぽい見た目をしているので (Hadamard 変換の問題を解いているのだから Hadamard 変換っぽい見た目には気づく)， $+ e_{000} - e_{100} - e_{010} + e_{110} + e_{001} - e_{101} - e_{011} + e_{111}$ とかそういうやつがほしい．それは $\sum_i (-1)^{\langle v, a_i \rangle} (-1)^{\langle v, b_i \rangle}$ とかで，そんなのが求まるかというと，よく見ると $\sum_i (-1)^{\langle v, a_i \oplus b_i \rangle}$ なのでうれしい (冷静さが必要)．これでできたのでまとめると，

解法

$\sum_i T^{0}, \sum_i T^{a_i}, \sum_i T^{b_i}, \sum_i T^{a_i \oplus b_i}, \sum_i T^{c_i}, \sum_i T^{a_i \oplus c_i}, \sum_i T^{b_i \oplus c_i}, \sum_i T^{a_i \oplus b_i \oplus c_i}$ のそれぞれを Hadamard 変換する．
各 $v$ に対して， $v$ 項目を集めて長さ $2^3$ の列にして Hadamard 逆変換すると， $(+ x + y + z)^{e_{000}} (- x + y - z)^{e_{100}} (+ x - y + z)^{e_{010}} \cdots$ の各指数が得られるので，計算する．
というのを並べて，Hadamard 逆変換すると答え．