题解 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}$
递推即可
当然矩阵快速幂也没人拦着你

1
2
3
4
5
6
7
8
9
10
11
12

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll f[1000010], n;
int () {
    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("%lldn", f[n]), 0;
}