cf230-C

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:

F1 = 1, F2 = 2, Fi = Fi - 1 + Fi - 2 (i > 2).
We’ll define a new number sequence Ai(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 integers nk (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;
}

本文链接:cf230-C

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:Rexdf,谢谢!^^


此条目发表在数论分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

:zsmilebig: :zsadbig: :zwiredbig: :zgreenhappy: more »

This site uses Akismet to reduce spam. Learn how your comment data is processed.