CC

自然万物都趋向从有序变得无序

0%

Yet Another Number Sequence CodeForces - 392C 矩阵快速幂

发表于 更新于 分类于 Valine：

题目链接:点我

题目

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 × i^k (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 modulo 1000000007 (109 + 7).

Input

The first line contains two space-separated integers n, k (1 ≤ n ≤ 1e17; 1 ≤ k ≤ 40).

Output

Print a single integer — the sum of the first n elements of the sequence Ai(k) modulo 1000000007 (1e9 + 7).

Example

Input

1 1

Output

1

Input

4 1

Output

34

Input

5 2

Output

316

Input

7 4

Output

73825

题意:

如果提上公式所说:计算 A1(k) + A2(k) + … + An(k), Ai(k) = Fi × i^k.

思路:

矩阵快速幂.
首先我们应该知道,(n+1)k(n+1)^k =$ k \choose k$$ n^k$ +$ k \choose k-1$ nk−1n^{k-1} + $ k \choose k-2$$n^{k-2}$ + … +$ k \choose 1$ n +$ k \choose 0$ n0n^0
我们令u(n+1,k) = (n+1)k(n+1)^k * F(n+1), v(n+1,k) = (n+1)k(n+1)^k * F(n)
根据斐波那契数列递推式:
u(n+1,k) = (n+1)k(n+1)^k * F(n+1)
= (n+1)k(n+1)^k * F(n) + (n+1)k(n+1)^k * F(n-1)
= ∑i=0k\sum_{i=0}^k (ki)k \choose i * nin^i * F(n) + ∑i=0k\sum_{i=0}^k (ki)k \choose i * nin^i * F(n-1)
= ∑i=0k\sum_{i=0}^k (ki)k \choose i * nin^i * F(n) + ∑i=0k\sum_{i=0}^k (ki)k \choose i * v(n,i)
v(n+1,k) = (n+1)k(n+1)^k * F(n)
= ∑i=0k\sum_{i=0}^k (ki)k \choose i * nin^i * F(n)
= ∑i=0k\sum_{i=0}^k (ki)k \choose i * u(n,i)
令Sn=A1(k) + A2(k) + ... + An(k)S_n = A_1(k) + A_2(k) + ... + A_n(k)
所以 Sn+1=Sn+u(n,k)S_{n+1} = S_n + u(n,k),
那么我们构造一个(2K+3) * (2k+3)的矩阵即可,这个矩阵大家根据上面的递推式在纸上写写就出来了,

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;
int c[45][45];
LL m;

struct mat{
    LL a[85][85];
    mat (){memset(a,0 ,sizeof(a)); }
    mat operator *(const mat q){
        mat c;
        for(int i = 1; i <= m; ++i)
            for(int k = 1; k <= m; ++k)
            if(a[i][k])
        for(int j = 1; j <= m; ++j){
            c.a[i][j] += a[i][k] * q.a[k][j];
            if (c.a[i][j] >= mod) c.a[i][j] %= mod;
        }return c;
    }
};


mat qpow(mat x, LL n){
    mat ans;
    for(int i = 1; i <= 84; ++i)
        ans.a[i][i] = 1;
    while(n){
        if (n&1) ans = ans * x;
        x = x * x;
        n >>= 1;
    }return ans;
}

void init(){
    for(int i = 0; i <= 41; ++i)
        c[i][0] = c[i][i] = 1;
    for(int i = 1; i <= 41; ++i)
        for(int j = 1; j < i; ++j)
        c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}

int main(){
    LL n, k;
    init();
    scanf("%lld %lld", &n, &k);
    mat ans;
    m = 2 * k + 3;
    ans.a[1][1] = 1;
    for(int i = 2; i <= m; ++i){
        ans.a[i][1] = 0;
        ans.a[1][i] = c[k][(i-2)%(k+1)];
    }for(int i = 2; i <= k+2; ++i)
        for(int j = 2; j <= i;++j)
            ans.a[i][j] = ans.a[i][j+k+1] = ans.a[i+k+1][j] =  c[i-2][j-2];
    ans = qpow(ans,n-1);
    LL sum = 0;
    for(int i = 1; i <= m; ++i)
        sum = (sum + ans.a[1][i]) % mod;
    printf("%lld\n",sum);
    return 0;
}