题解 P4451 [国家集训队]整数的lqp拆分

题面
设{f_i}为斐波那契数列,生成函数为F(x)
{g_i}为答案的数列,生成函数为G(x)
强行钦定$g_0 = 1$
那么

$$G(x) = \sum_{i=0}^\infty F^i(x) = \frac 1{1-F(x)}$$

斐波那契数列生成函数的闭形式为$F(x) = \frac x{1-x-x^2}$
带进去

$$G(x) = \frac 1{1-\frac x{1-x-x^2}}$$ $$= 1 + \frac x{1-2x-x^2}$$

那个1是强行钦定$g_0=1$的结果，不用管

$$G(x) = x + 2xG(x) + x^2G(x)$$

那么$g_i=2*g_{i-1}+g_{i-2}$
递推即可
当然矩阵快速幂也没人拦着你

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll f[1000010], n;
int main() {
    scanf("%lld", &n);
    f[0] = 0;
    f[1] = 1;
    for(int i = 2; i <= n; i++) f[i] = (2 * f[i - 1] + f[i - 2]) % mod;
    return printf("%lld\n", f[n]), 0;
}