Description
Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
F = 1, F = 2, F = F + F (i > 2).
We'll define a new number sequence A(k) by the formula:
A(k) = F × i (i ≥ 1).
In this problem, your task is to calculate the following sum: A(k) + A(k) + ... + A(k). The answer can be very large, so print it modulo 1000000007(10 + 7).
Input
The first line contains two space-separated integers n, k(1 ≤ n ≤ 10; 1 ≤ k ≤ 40).
Output
Print a single integer — the sum of the first n elements of the sequence A(k) modulo 1000000007(10 + 7).
Sample Input
Input
1 1
Output
1
Input
4 1
Output
34
Input
5 2
Output
316
Input
7 4
Output
73825 解题思路:
这是一道矩阵快速幂求多项式的应用,思路很清晰:找到各个量之间的递推关系,用矩阵求幂转移状态。问题的关键在于推导A(n,k),sumA(n),
F(n)之间的关系。过程如下:
1.令 U(n+1,k)=F(n+1)*(n+1)^k;
V(n+1,k)=F(n)*(n+1)^k;
Sum(n)=∑[i=1~n]A(i,k);
2.利用二项式定理将(1+i)^n展开;
则 U(n+1,k)=∑[i=0~k]C(i,k)*F(n)*(n)^i+∑[i=0~k]C(i,k)*F(n-1)*(n)^i
=∑[i=0~k]C(i,k)*U(n,i)+∑[i=0~k]C(i,k)*V(n,i);
同理 V(n+1,k)=∑[i=0~k]C(i,k)*U(n,i);
Sum(n)=Sum(n-1)+U(n,k);
3.状态转移用矩阵向量表示:
sum(n-1) | sum(n) | |
U(n,k) | U(n+1,k) | |
... | ... | |
U(n,0) | => | U(n+1,0) |
V(n,k) | V(n+1,k) | |
... | ... | |
V(n,0) | V(n+1,0) |
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <time.h>
#include <assert.h>
#define time_ printf("time : %f\n",double(clock())/CLOCKS_PER_SEC)
using namespace std;
#define maxk 40
#define MOD 1000000007
#define mod_(x) (x%MOD) typedef long long LL;
LL n;
int k; struct Matrix{
int row,col;
int m[*maxk+][*maxk+];
Matrix(int r=,int c=){
row=r;
col=c;
memset(m, , sizeof m);
}
void operator=(const Matrix& m2){
memcpy(m, m2.m, sizeof m);
}
};
Matrix operator*(const Matrix& a,const Matrix& b){
Matrix c(a.row,b.col);
for(int i=;i<c.row;i++)
for(int j=;j<c.col;j++){
for(int p=;p<a.col;p++){
c.m[i][j]=(c.m[i][j]+LL(a.m[i][p])*b.m[p][j])%MOD;
//assert(c.m[i][j]>=0);
}
}
return c;
}
Matrix C;
void set_C(){
for(int i=k;i>=;i--)
for(int j=k;j>=i;j--){
if(j==k||j==i)
C.m[i][j]=;
else
C.m[i][j]=(C.m[i+][j]+C.m[i+][j+])%MOD;
}
}
void cpy_C(Matrix& a,int pi,int pj){
int len=k+;
for(int i=;i<len;i++)
for(int j=;j<len;j++)
a.m[pi+i][pj+j]=C.m[i][j];
}
void set_M(Matrix& a){
a.m[][]=,a.m[][]=;
cpy_C(a, , );
cpy_C(a, k+, );
cpy_C(a, , k+);
}
Matrix pow_mod(Matrix& a,LL n){
if(n==) return a;
Matrix temp=pow_mod(a, n/);
temp=temp*temp;
if(n%){
temp=temp*a;
}
return temp;
}
int pow_2(int n){
if(n==) return ;
int temp=pow_2(n/)%MOD;
temp=int((LL(temp)*temp)%MOD);
if(n%)
temp=(temp*)%MOD;
return temp;
}
int main(int argc, const char * argv[]) {
while(scanf("%lld%d",&n,&k)==){
if(n==){
printf("%d\n",);
continue;
}
set_C();
Matrix I(*k+,*k+);
set_M(I);
Matrix A(*k+,);
A.m[][]=;
for(int i=;i<k+;i++)
A.m[i][]=pow_2(k+-i+);
for(int i=k+;i<*k+;i++)
A.m[i][]=pow_2(*k+-i);
Matrix temp=pow_mod(I, n-);
A=temp*A;
printf("%d\n",A.m[][]);
//time_;
}
return ;
}