题面

题解

我对生成函数一无所知

我们设\(F(x)\)为斐波那契数列的生成函数，\(G(x)\)为答案的生成函数，那么容易得到递推关系

\[g_n=\sum_{i=0}^{n-1}f_ig_{n-i}+f_n\]

其中\(g_0=0,g_1=1\)

那么写成生成函数的形式就是

\[G=FG+F\]

\[G={F\over 1-F}\]

我们考虑一下\(F\)，因为

\[F(x)=\sum_{i=1}^\infty f_ix^i\]

\[xF(x)=\sum_{i=2}^\infty f_{i-1}x^i\]

上面的柿子减去下面的柿子

\[(1-x)F(x)=x+\sum_{i=2}^\infty f_{i-2}x^i\]

即

\[(1-x)F(x)=x+x^2F(x)\]

解得

\[F(x)={x\over 1-x-x^2}\]

代入可解出

\[G(x)={x\over 1-2x-x^2}\]

我们把\(1-2x-x^2\)因式分解一下

\[G(x)={x\over \left(1-(1+\sqrt{2})x\right)\left(1-(1-\sqrt{2})x\right)}\]

然后裂项

\[G(x)={1\over 2\sqrt{2}}{1\over \left(1-(1+\sqrt{2})x\right)}-{1\over 2\sqrt{2}}{1\over \left(1-(1-\sqrt{2})x\right)}\]

那么现在就变成两个等比数列求和的形式了，可以直接求出\(g_n\)的通项公式

\[g_n={(1+\sqrt{2})^n-(1-\sqrt{2})^n\over 2\sqrt{2}}\]

听说大佬们用生成函数只要五行就能写完题解……然而我并看不懂它们在写什么……

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;const int P=1e9+7,s=59713600;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);    return res;}int main(){//  freopen("testdata.in","r",stdin);    int n;scanf("%d",&n);    printf("%d\n",mul(dec(ksm(s+1,n),ksm(P+1-s,n)),ksm(mul(s,2),P-2)));    return 0;}