yukicoder No.980 Fibonacci Convolution Hard

https://yukicoder.me/problems/no/980

もとの数列の母関数を二乗したものが 2000000 項目までわかればよい。もとの数列の母関数が分数の形で書けるので、二乗しても分数の形で書ける。分子と分母が求まったら、分数の形から無限和の形に書き換えればよい。これは自然数多項式の割り算の筆算と同じようにできる。下ではフィボナッチ数の母関数 $x^2 / (1-x-x^2)$ に対して筆算を行っている。

f:id:pekempey:20200214112701j:plain