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}^{\mathrm{\infty }}{g}^i}\right)}_0/(n+1)$ を求めればよい。

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

${\mathrm{\forall }}_{i}1-\mathrm{W}\mathrm{H}\mathrm{T}(g{)}_i\ne 0$ であることは、各項の分母が $n+1$ で、分子が $-n$ から $n$ の間にあることから言える。

実装例

codeforces.com