# yukicoder No.2156 ぞい文字列

形式的冪級数解

## 問題

[yukicoder No.2156 ぞい文字列](https://yukicoder.me/problems/no/2156)

## 解説

「い」で区切ると次のようになっている．

- 次の形の文字列を $1$ つ以上
- 「ぞ」 $1$ 文字以上 +「い」
- +「ぞ」 $0$ 文字以上

「ぞ」 $1$ 文字以上 +「い」の形の長さ $n$ の文字列の個数を係数に持つ形式的冪級数は
\\[x^2+x^3+\cdots=\frac{x^2}{1-x}\\]
であるから，求める値は次で得られる．
\begin{align*}
&[x^N]\sum_{k\geq 1}\left(\frac{x^2}{1-x}\right)^k\frac{1}{1-x}\\
&=[x^N]\frac{\frac{x^2}{1-x}}{1-\frac{x^2}{1-x}}\cdot\frac{1}{1-x}\\
&=[x^N]\frac{x^2}{(1-x)(1-x-x^2)}\\
\end{align*}

Bostan-Mori 法などを用いて計算量 $O(\log N)$ で計算できる．