【[国家集训队]整数的lqp拆分】

生成函数一血祭。

传送门

首先设答案为$g(n)$，有一个显然的递推式：$g(n)=\sum_{i=1}^nfib_{i}\times g_{n-i}$，另外$g_0=1​$

那么他的生成函数：
$$
G(x)=\sum_{n=0}g_nx^n
$$

$$
=\sum_{n=0}(\sum_{i=0}^{n-1}fib_ig_{n-i}+[n=0])x^n
$$

$$
=1+\sum_{n=0}x^n\sum_{i=0}^{n-1}fib_ig_{n-i}
$$

$$
=1+\sum_{n=0}\sum_{i=0}^{n-1}fib_ix^i\times g_{n-i}x^{n-i}
$$

就可以看成：
$$
G(x)=1+F(x)\times G(x)
$$
$F(x)$是斐波那契数列的生成函数，众所周知：
$$
F(x)=\frac{x}{1-x-x^2}
$$
那么：
$$
G(x)=\frac{1-x-x^2}{1-2x-x^2}=1+\frac{x}{1-2x-x^2}
$$
$1-2x-x^2$可以因式分解成$(1-(1+\sqrt2)x)(1-(1-\sqrt2)x)$

两项的差是$2\sqrt2x$，那么我们来把他裂项：
$$
G(x)=1+\frac{x}{2\sqrt2x}(\frac{1}{1-(1+\sqrt2)x}-\frac{1}{1-(1-\sqrt2)x})
$$
不管那个一，我们已经得到了想要的式子，这是一个第$n$系数为$\frac{((1+\sqrt2)x)^n-((1-\sqrt2)x)^n}{2\sqrt2}$的多项式，同时这个系数也是我们要求的答案。

所以我们求出了$G(x)​$的通项

PS： $\sqrt2≡59713600(mod\ 1e9+7)$

#include<cstdio>
#include<iostream>
#define re register
#define mod 1000000007
const int s2=59713600;
using namespace std;
inline int add(re int x,re int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(re int x,re int y){return x-y<0?x-y+mod:x-y;}
inline int mul(re int x,re int y){return 1ll*x*y-1ll*x*y/mod*mod;}
inline int ksm(int a,int b){
    int res=1;
    while (b){
        if (b&1) res=mul(res,a);
        a=mul(a,a); b>>=1;
    }
    return res;
}
int main(){
    int n; scanf("%d",&n);
    printf("%d\n",mul(dec(ksm(add(1,s2),n),ksm(dec(1,s2),n)),
    ksm(mul(2,s2),mod-2)));
    return 0;
}