原题链接
斐波那契数列的生成函数 ：
\[F(x) = \frac{x}{1-x-x^2}
\]
答案的生成函数 ：
\[G(x) = \sum_{i=0}^{inf} F(x)^i
\]
打个表出来：
1
2
5
12
29
70
169
408
985
2378
5741
13860
33461
80782
195025
470832
1136689
2744210
6625109
15994428
发现 \(ans[i] = ans[i-1]\times 2 + ans[i-2]\)。
矩阵快速幂即可。