摘要：
YetAnotherNumberSequenceDescriptionEveryoneknowswhattheFibonaccisequenceis.Thissequencecanbedefinedbytherecurrencerelation:F1=1,F2=2,Fi=Fi-1+Fi-2(i˃2).We'lldefineanewnumbersequenceAi(k)bytheformula:Ai
Description
Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
F1 = 1, F2 = 2, Fi = Fi - 1 + Fi - 2(i > 2). We'll define a new number sequenceAi(k)by the formula:
Ai(k) = Fi × ik(i ≥ 1). In this problem, your task is to calculate the following sum:A1(k) + A2(k) + ... + An(k). The answer can be very large, so print it modulo1000000007(109 + 7).
Input
The first line contains two space-separated integersn,k(1 ≤ n ≤ 1017;1 ≤ k ≤ 40).
Output
Print a single integer — the sum of the firstnelements of the sequenceAi(k)modulo1000000007(109 + 7).
Sample Input
Input1 1Output1Input4 1Output34Input5 2Output316Input7 4Output73825
【分析】
哈哈照着上一题的方法我就弄出来了~~
应该是形如 x^k的形式，x很大，k较小的时候可以用二项式定理展开，求递推式然后矩阵加速。。
就这样，qpow n次就好啦~
代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespacestd; 9 #define Mod 1000000007 10 #define Maxn 110 11 #define LL long long 12 13 structnode 14 { 15 LL a[Maxn][Maxn]; 16 }t[5]; 17 18 LL c[Maxn][Maxn]; 19 LL n,k; 20 21 voidinit() 22 { 23 memset(c,0,sizeof(c)); 24 for(LL i=0;i<=80;i++) c[i][0]=1; 25 for(LL i=1;i<=80;i++) 26 for(LL j=1;j<=80;j++) 27 c[i][j]=(c[i-1][j-1]+c[i-1][j])%Mod; 28 } 29 30 voidget_m() 31 { 32 for(LL i=k+1;i<=2*k+1;i++) 33 { 34 for(LL j=0;j<=i-k-1;j++) t[0].a[i][j]=c[i-k-1][j]; 35 for(LL j=i+1;j<=2*k+2;j++) t[0].a[i][j]=0; 36 } 37 for(LL i=0;i<=k;i++) 38 { 39 for(LL j=0;j<=i;j++) t[0].a[i][j]=t[0].a[i][j+k+1]=c[i][j]; 40 for(LL j=i+1;j<=k;j++) t[0].a[i][j]=t[0].a[i][j+k+1]=0; 41 t[0].a[i][2*k+2]=0; 42 } 43 for(LL i=0;i<=2*k+1;i++) t[0].a[2*k+2][i]=0; 44 t[0].a[2*k+2][2*k+2]=t[0].a[2*k+2][k]=1; 45 } 46 47 voidget_un() 48 { 49 memset(t[1].a,0,sizeof(t[1].a)); 50 for(LL i=0;i<=2*k+2;i++) t[1].a[i][i]=1; 51 } 52 53 voidmul(LL x,LL y,LL z) 54 { 55 for(LL i=0;i<=2*k+2;i++) 56 for(LL j=0;j<=2*k+2;j++) 57 { 58 t[2].a[i][j]=0; 59 for(LL l=0;l<=2*k+2;l++) 60 t[2].a[i][j]=(t[2].a[i][j]+t[y].a[i][l]*t[z].a[l][j])%Mod; 61 } 62 t[x]=t[2]; 63 } 64 65 voidqpow(LL b) 66 { 67 get_un(); 68 while(b) 69 { 70 if(b&1) mul(1,0,1); 71 mul(0,0,0); 72 b>>=1; 73 } 74 } 75 76 intmain() 77 { 78 init(); 79 scanf("%lld%lld",&n,&k); 80 get_m(); 81 qpow(n); 82 LL ans=0; 83 for(LL i=0;i<2*k+2;i++) ans=(ans+t[1].a[2*k+2][i])%Mod; 84 printf("%lld ",ans); 85 return 0; 86 }
2016-09-2616:11:26