CodeForces392C Yet Another Number Sequence题解(矩阵快速幂+二项式定理)

Description

传送门:CodeForces - 392C

Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
\(F_1 = 1,F_2 = 2,F_i = F_{i-1}+F_{i-2}(i>2)\)
We'll define a new number sequence \(A_i(k)\)by the formula:
\(A_i(k) = F_i * i^k(i \ge 1)\)
In this problem, your task is to calculate the following sum:\(A_1(k)+A_2(k)+\cdots+A_n(k)\).The answer can be very large, so print it modulo \(1000000007\)(\(10^9+7\)).


Input

The first line contains two space-separated integers \(n\), \(k\) (1 ≤ \(n\) ≤ \(10^{17}\); 1 ≤ \(k\) ≤ 40).

Output

Print a single integer — the sum of the first \(n\) elements of the sequence \(A_i(k)\) modulo \(1000000007 (10^9 + 7).\)

Sample Input

1
2
3
4
1 1
4 1
5 2
7 4

Sample Output

1
2
3
4
1
34
316
73825

题目大意

计算\(\displaystyle \sum_{i=1}^{n}{fib(i)*{i^k}}\),其中\(fib\)是斐波那契数列。

思路

这个题很容易可以想到矩阵快速幂,但是难点是如何找到转移矩阵。
首先我们要知道二项式定理,根据二项式定理,我们可以拆一下\((n+1)^k\)
\[(n+1)^k = C(^0_k)*{n^0} + C(^1_k)*{n^1}+ \cdots + C(^k_k)*{n^k}\] \[(n+1)^k = \displaystyle\sum_{i=0}^{k}(C(^i_k)*{n^i})\]
我们记\(g_1(n,k) = fib(n)*{n^k}\)\(g_2(n,k) = fib(n-1)*{n^k}\)
\[ \begin{align} g_1(n+1,k) &= fib(n+1)*(n+1)^k \\ &= (fib(n)+fib(n-1))*(n+1)^k \\ &= (fib(n)+fib(n-1))*(\displaystyle\sum_{i=0}^{k}{C(^i_k)*{n^i})} \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*(fib(n)*{n^i+fib(n-1)*{n^i})}} \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*(g_1(n,i)+g_2(n,i))} \\ g_2(n+1,k) &=fib(n)*(n+1)^k \\ &= fib(n)*(\displaystyle\sum_{i=0}^{k}{C(^i_k)*{n^i}}) \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*(fib(n)*{n^i})} \\ &= \displaystyle\sum_{i=0}^{k}{C(^i_k)*g_1(n,i)} \end{align} \] 根据式子我们可以得到转移矩阵。
\[ \begin{bmatrix}g_1(n+1,0)\\g_1(n+1,1)\\\vdots\\g_1(n+1,k)\\g_2(n+1,0)\\g_2(n+1,1)\\\vdots\\g_2(n+1,k)\\sum(n+1,k)\end{bmatrix} = \begin{bmatrix}C(^0_k)&C(^1_k)&\cdots&C(^k_k)&C(^0_k)&C(^1_k)&\cdots&C(^k_k)\\0&C(^1_k)&\cdots&C(^k_k)&0&C(^1_k)&\cdots&C(^k_k)\\\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&C(^k_k)&0&0&\cdots&C(^k_k)\\C(^0_k)&C(^1_k)&\cdots&C(^k_k)&0&0&\cdots&0\\0&C(^1_k)&\cdots&C(^k_k)&0&0&\cdots&0\\\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&C(^k_k)&0&0&\cdots&C(^k_k)\\0&0&\cdots&1&0&0&\cdots&1\end{bmatrix}*\begin{bmatrix}g_1(n,0)\\g_1(n,1)\\\vdots\\g_1(n,k)\\g_2(n,0)\\g_2(n,1)\\\vdots\\g_2(n,k)\\sum(n,k)\end{bmatrix} \] 然后我们使用矩阵快速幂,求出\(sum(n,k)\)就是最后的答案。

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/************************************************************
> File Name: cf.cpp
> Author: TSwiftie
> Mail: 2224273204@qq.com
> Created Time: Fri 11 Oct 2019 10:23:04 AM CST
************************************************************/

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
#define lowbit(x) (x&-x)
#define lc o<<1
#define rc o<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
const int MOD = 1e9+7;
const double PI = acos(-1.0);
const double EXP = 1e-8;
ll N, M, P;
ll C[85][85];
struct Matrix{
ll m[85][85];
};
Matrix A, I;
//组合数矩阵
void get_C(){
memset(C,0,sizeof C);
C[0][0] = 1;
for(int i = 1;i <= 82;i++){
C[0][i] = C[i][i] = 1;
for(int j = 1;j <= i;j++)
C[j][i] = (C[j][i-1]+C[j-1][i-1])%MOD;
}
}
//初始化对角阵
void make_I(int k){
memset(I.m,0,sizeof I.m);
for(int i = 0;i <= 2*(k+1);i++)
for(int j = 0;j <= 2*(k+1)+1;j++)
if(i==j)
I.m[i][j] = 1;
}
//转移矩阵
void make_A(int k){
memset(A.m,0,sizeof A.m);
for(int i = 0;i <= k;i++)
for(int j = 0;j <= i;j++)
A.m[i][j] = C[j][i];
for(int i = 0;i <= k;i++)
for(int j = 0;j <= i;j++)
A.m[i+k+1][j] = C[j][i];
for(int i = 0;i <= k;i++)
for(int j = k+1;j <= 2*(k+1)-1;j++)
A.m[i][j] = C[j-k-1][i];
A.m[2*(k+1)][k] = 1;
A.m[2*(k+1)][2*(k+1)] = 1;
}
//矩阵乘法
Matrix mul(Matrix a,Matrix b){
Matrix ans;
for(int i = 0;i <= N;i++)
for(int j = 0;j <= M;j++){
ans.m[i][j] = 0;
for(int k = 0;k <= P;k++)
ans.m[i][j] = (ans.m[i][j] + a.m[i][k]*b.m[k][j])%MOD;
ans.m[i][j] %= MOD;
}
return ans;
}
//矩阵快速幂
Matrix ksm(Matrix a,ll b){
Matrix res = I;
while(b){
if(b&1)
res = mul(res,a);
a = mul(a,a);
b >>= 1;
}
return res;
}
int main(void){
ll n;
int k;
get_C();
while(~scanf("%lld %d",&n,&k)){
if(n==1){
printf("1\n");
continue;
}else{
make_A(k);
make_I(k);
N = M = P = 2*(k+1);
Matrix ans = ksm(A,n);
ll num = 0;
for(int i = 0;i < M;i++)
num = (num + ans.m[2*(k+1)][i])%MOD;
printf("%lld\n",num);
}
}
return 0;
}

本文标题:CodeForces392C Yet Another Number Sequence题解(矩阵快速幂+二项式定理)

文章作者:TSwifite

发布时间:2019年10月12日 - 13:10

最后更新:2019年11月08日 - 23:11

原始链接:http://tswiftie.com/CodeForces392C-Yet-Another-Number-Sequence题解-矩阵快速幂-二项式定理/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%