beet's soil

競プロのことなど

Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) - E. No Game No Life

書き忘れてた

問題

codeforces.com

解法

遷移を $g$ とすると、 $ \left (\displaystyle \sum_{i=0}^{\infty} g^{i} \right )_0 / (n+1) $ を求めればよい。

ところで、これを使うと $1 / (1 - g)$ で求まることが分かり、解けた。

$\forall_i 1 - \mathrm{WHT}(g)_i \neq 0$ であることは、各項の分母が $n + 1$ で、分子が $-n$ から $n$ の間にあることから言える。

実装例

codeforces.com