H - Nim Counting Editorial
by
Mitsubachi
公式解説では等比数列の和を求めるときの $0$ 除算の話がありましたが、これを回避する方法を説明します。
数列 $V$ に対して $V^i$ を $i$ 個の $V$ を xor convolution した結果として、 $V^0 + V^1 + \dots + V^N$ が分かれば良いです。( $+$ は数列の各要素について和をとったものです。)
下の説明では、数列の積は xor convolution によるものとします。
$[1]$ $N$ が偶数の時
$V^0 + V^1 + \dots + V^N = \left( V^0 + V^1 + \dots + V^{\frac{N}{2}} \right) \left( V^0 + V^{\frac{N}{2}} \right) - V^{\frac{N}{2}}$ です。
$[2]$ $N$ が奇数の時
$V^0 + V^1 + \dots + V^N = \left( V^0 + V^1 + \dots + V^{\frac{N - 1}{2}} \right) \left( V^0 + V^{\frac{N + 1}{2}} \right)$ です。
いずれの場合でも、再帰的に求めることができるものとなります。 \(V^i\) も再帰的に求めることができますが、アダマール変換をした後各要素を \(i\) 乗して逆アダマール変換をすると楽です。
posted:
last update:
