订阅
C. Yet Another Number Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
Input
The first line contains two space-separated integers n, k (1 ≤ n ≤ 1017; 1 ≤ k ≤ 40).
Output
Print a single integer — the sum of the first n elements of the sequence Ai(k) modulo 1000000007 (109 + 7).
Sample test(s)
input
1 1
output
1
input
4 1
output
34
input
5 2
output
316
input
7 4
output
73825
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
const int D(83);
const long long MOD(1e9+7);
struct Matrix{
long long v[D][D];
int d;
Matrix operator *(const Matrix& b)const{
Matrix ret;
ret.d=d;
for(int i=0;i<d;i++)
for(int j=0;j<d;j++){
ret.v[i][j]=0;
for(int k=0;k<d;k++)ret.v[i][j]+=(v[i][k]*b.v[k][j])%MOD,ret.v[i][j]%=MOD;
}
return ret;
}
Matrix operator^(long long p){
Matrix ret,tmp=*this;
memset(ret.v,0,sizeof(ret.v));
ret.d=d;
for(int i=0;i<d;i++)ret.v[i][i]=1;
while(p){
if(p&1){
ret=ret*tmp;
}
p>>=1;
tmp=tmp*tmp;
}
return ret;
}
void init(int k){
memset(v,0,sizeof(v));
d=2*(k+1)+1;
v[0][0]=1;
for(int i=0;i<=k;i++){
//v[1+i][k+1]=2;v[1+i][1+i]=2;//LT
v[1+i][k+1]=1;v[1+i][1+i]=1;//LT
v[1+i][2*k+2]=1;v[1+i][2+i+k]=1;//RT
v[2+k+i][k+1]=1;v[2+k+i][1+i]=1;//LB
//v[2+k+i][2*k+2]=1;v[2+k+i][2+k+i]=1;//RB
}
int dx[]={0,0,k+1,k+1};
int dy[]={0,k+1,0,k+1};
for(int i=k-1;i;i--)
for(int j=i+1;j<k+1;j++)
for(int k=0;k<4;k++){
v[dx[k]+i][dy[k]+j]=(v[dx[k]+i+1][dy[k]+j]+v[dx[k]+i+1][dy[k]+j+1])%MOD;
}
for(int i=1;i<=k+1;i++){
v[0][i]=v[0][k+1+i]=v[1][k+1+i];
}
}
};
int main(){
_;
long long n;
int k;
cin>>n>>k;
Matrix A;
A.init(k);
A=A^(n-1);
long long ans=0;
for(int i=0;i<2*(k+1)+1;i++)ans+=A.v[0][i],ans%=MOD;
cout<<ans<<endl;
return 0;
}