正题

      设斐波那契数列的原函数为

      答案就是求

      我们先把F(x)的封闭形式推导出来:

      

     带进答案中,可以得到

     递推式子显然,然后做以10为基的矩阵快速幂即可.

#include<bits/stdc++.h> using namespace std; char s[10010]; const int mod=1000000007; void upd(int&x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);} struct Matrix{ int a[2][2]; }tot,x; int n; Matrix operator*(Matrix A,Matrix B){ Matrix p; memset(p.a,0,sizeof(p.a)); for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++) upd(p.a[i][j],1ll*A.a[i][k]*B.a[k][j]%mod); return p; } int main(){ scanf("%s",s+1);n=strlen(s+1); x.a[0][0]=2;x.a[0][1]=x.a[1][0]=tot.a[0][0]=tot.a[1][1]=1; for(int i=n;i>=1;i--){ int t=s[i]-'0'; for(int j=1;j<=t;j++) tot=tot*x; x=x*x*x*x*x*x*x*x*x*x; } printf("%d\n",tot.a[0][1]); }