# ニワンゴくんとゲーム 別解

#### 問題文
[リンク](https://atcoder.jp/contests/dwacon2018-final-open/tasks/dwacon2018_final_d)

#### 解法
$\left[x^n\right]F(x)=$「1から始めて魔力をちょうど$n$になるように操作する方法の数」といった母関数を考えます。
操作について考えることで$$F(x) = x + xF(x) + F(x^2) + xF(x^2)$$という式が立ちます。
$F(x)$ について解くと
\begin{aligned}
F(x) &= \frac{x}{1-x} + \frac{(1+x)F(x^2)}{1-x}\\
\left[x^n\right]F(x) &= [x^n]\frac{x}{1-x} + [x^n]\frac{(1+x)F(x^2)}{1-x}\\
&= [x^n]\frac{x}{1-x}+[x^n]\frac{(1+2x+x^2)F(x^2)}{1-x^2}
\end{aligned}
と書けます。
左の項の計算は容易で、右の項は Bostan-Mori の要領で適当な多項式$P$ を用いて $[x^{\lfloor\frac{n}{2}\rfloor}] \frac{PF(x)}{1-x}$を計算することに帰着できます。
これを繰り返し適用することで求めたいものは適当な多項式の列 $P_i$ を用いて
$$[x^n]F(x) = \sum_{i \geq 1} [x^{\lfloor n/2^{i-1}\rfloor}]\frac{xP_i}{(1-x)^i}$$
の形で書けることがわかり、これは負の二項係数やBostan-Moriで計算可能です。

2023/08/27 追記
もう少し一般化できそうな形が思いついたので

$$F(x) = \frac{A(x) + B(x)F(x^2)}{C(x)}$$

という形の $F(x)$ について
$$\left[ x^n\right]\frac{P(x) + Q(x)F(x)}{R(x)}$$
を計算したいとしよう。
$$ \left[ x^n\right]\frac{P(x) + Q(x)F(x)}{R(x)} = \left[ x^n\right]\frac{P(x)C(x) + Q(x)A(x) + Q(x)B(x)F(x^2)}{R(x)C(x)} $$
となり、分子分母に $R(-x)C(-x)$ をかけると分母は偶関数となって BostanMori でみる形となり、適当な多項式 $P'(x), Q'(x), R'(x)$ を用いて
$$\left[ x^{\lfloor\frac{n}{2}\rfloor}\right]\frac{P'(x) + Q'(x)F(x)}{R'(x)}$$
の計算をすることに帰着できます。
これを$n=0$となるまで続ければあとは0次の項で計算できるようになります。
計算量は入力の $A, B, C$ の最大次数を $M$, $P, Q, R$の最大次数を $L$ と置き、長さ$K$の畳み込みの計算量を$\text{MUL}(K)$ と置くと$O(\text{MUL}(L+ M\log N) \log N)$ となります。

このページで解説した問題なら $A=x,B=1+x,C=1-x,P=0, Q=1,R=1$ で計算すればいい。