Codeforces 392C. Yet Another Number Sequence

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define ll long long 
 5 using namespace std ;
 6 int n ,c[50][50] ={1} ;
 7 const int mod = 1e9+7 ;
 8 struct MAT{
 9     ll a[90][90] ;
10     MAT(){ memset( this ,0 ,sizeof(MAT) ) ; }
11 };
12 MAT multi( MAT a ,MAT b ){
13     MAT ret;
14     for( int i = 0 ;i < n ;i ++ )
15         for( int j = 0 ;j < n ;j ++ ){
16             for( int k = 0 ;k < n ;k ++ ){
17                 ret.a[i][j] += a.a[i][k] * b.a[k][j];
18                 ret.a[i][j] %= mod;
19             }
20         }
21     return ret;
22 }
23 MAT Qpow( MAT a ,ll b ){
24     MAT ret;
25     for( int i = 0 ;i < n ;i ++ ) 
26         ret.a[i][i]=1;
27     while( b ){
28         if( b & 1 )
29             ret = multi( ret ,a );
30         b /= 2;
31         a = multi( a ,a );
32     }
33     return ret;
34 }
35 int main(){
36     ll t ,k ;
37     cin >> t >> k ;
38     n = 2 * k + 3 ;
39     MAT base ;
40     for( int i = 0 ;i <= k ;i ++ ){
41         c[i][0] = 1 ;
42         for( int j = 1 ;j <= i ;j ++ ){
43             c[i][j] = ( c[i-1][j-1] + c[i-1][j] ) % mod ;
44         }
45     }
46     for( int i = 0 ;i <= k ;i ++ ){
47         for( int j = 0 ;j <= i ;j ++ ){
48             base.a[i+k+1][j] = base.a[i][j] = base.a[i][j+k+1] = c[i][j] ;
49         }
50     }
51     base.a[k+k+2][k] = base.a[k+k+2][k+k+2] = 1 ;
52 
53     MAT ans = Qpow( base ,t ) ;
54     ll a = 0 ;
55     for( int i = 0 ;i < 2*k+2 ;i ++ ) 
56         a = ( a + ans.a[k+k+2][i] ) % mod  ;
57     cout << a << endl ;
58 }