1.斐波那契数列问题引入
对于求斐波那契数列第n项的问题，相信大家已经非常熟悉了，下面做一下简单的描述。
斐波那契数列数学问题：
对于一个斐波那契数列满足公式：
f
(
n
)
=
f
(
n
?
1
)
+
f
(
n
?
2
)
f(n) = f(n-1)+f(n-2)
f(n)=f(n?1)+f(n?2)
特别的，
f
(
0
)
=
0
,
f
(
1
)
=
1
,
f
(
2
)
=
1
f(0)=0,f(1)=1,f(2)=1
f(0)=0,f(1)=1,f(2)=1
求给定n，求
f
(
n
)
f(n)
f(n)的值
当给定的n限制比较小时，我们可以采用递推的方式求解，但是当n给的范围比较大时，就显然不能采用递推的方式了。
对于斐波那契的其它求解方法，下面这篇文章有一个比较清楚的描述。
斐波那契的几种求解方法
本文着重探讨斐波那契的矩阵快速幂求解方式。
2.矩阵快速幂求解斐波那契数列
前导知识：矩阵乘法运算，快速幂思想
斐波那契递推公式：
f
(
n
)
=
f
(
n
?
1
)
+
f
(
n
?
2
)
f(n) = f(n-1)+f(n-2)
f(n)=f(n?1)+f(n?2)
对于这个公式，我们首先就是要构造一个矩阵乘积的等式,这个等式有以下特点：
- 矩阵等式刚好可以看成Y(n)和Y(n-1)的递推公式
比如
[
f
(
n
)
f
(
n
?
1
)
]
=
[
f
(
n
?
1
)
f
(
n
?
2
)
]
[
1
1
1
0
]
\begin{bmatrix} f(n)&f(n-1) \end{bmatrix}=\begin{bmatrix} f(n-1)&f(n-2) \end{bmatrix}\begin{bmatrix} 1&1\\1&0 \end{bmatrix}
[f(n)?f(n?1)?]=[f(n?1)?f(n?2)?][11?10?] - 在递推的等式中出现数字的矩阵不能和
n相关，也就是必须全部为数字
构造这样的等式首先就是要得到需要递推的矩阵表达式，对于斐波那契数列来说，就是上面举例的一个矩阵等式，首先需要想到
[
f
(
n
)
f
(
n
?
1
)
]
\begin{bmatrix} f(n)&f(n-1) \end{bmatrix}
[f(n)?f(n?1)?]（这个感觉确实没有办法解释怎么构造的，因为斐波那契是基础，更多的递推构造都是和斐波那契很相似的）
那么右边就是
[
f
(
n
?
1
)
f
(
n
?
2
)
]
\begin{bmatrix} f(n-1)&f(n-2) \end{bmatrix}
[f(n?1)?f(n?2)?]
然后在后边乘一个矩阵需要让等式成立，可以求出是
[
1
1
1
0
]
\begin{bmatrix} 1&1\\1&0 \end{bmatrix}
[11?10?]
最后得到
[
f
(
n
)
f
(
n
?
1
)
]
=
[
f
(
n
?
1
)
f
(
n
?
2
)
]
[
1
1
1
0
]
\begin{bmatrix} f(n)&f(n-1) \end{bmatrix}=\begin{bmatrix} f(n-1)&f(n-2) \end{bmatrix}\begin{bmatrix} 1&1\\1&0 \end{bmatrix}
[f(n)?f(n?1)?]=[f(n?1)?f(n?2)?][11?10?]
这就是一个递推公式，求
f
(
n
)
f(n)
f(n)的话,从
[
f
(
1
)
f
(
0
)
]
\begin{bmatrix} f(1)&f(0) \end{bmatrix}
[f(1)?f(0)?]开始，那么
[
f
(
n
)
f
(
n
?
1
)
]
=
[
f
(
1
)
f
(
0
)
]
[
1
1
1
0
]
n
?
1
\begin{bmatrix} f(n)&f(n-1) \end{bmatrix}=\begin{bmatrix} f(1)&f(0) \end{bmatrix}\begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{n-1}
[f(n)?f(n?1)?]=[f(1)?f(0)?][11?10?]n?1
这个
[
1
1
1
0
]
n
?
1
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}
[11?10?]n?1就可以用矩阵快速幂求解，最后根据矩阵的一一对应相等的性质，求出
f
(
n
)
f(n)
f(n)
注意： 矩阵的乘法是不具有交换律的
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2;
int n,m;
void mul(int a[][N],int b[][N],int t[][N])
{
static int c[N][N];
memset(c,0,sizeof c);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
c[i][j]=(c[i][j]+(ll)a[i][k]*b[k][j]+m)%m;
memcpy(t,c,sizeof c);
}
int main()
{
int a[N][N]={1,0};
int b[N][N]={{1,1},{1,0}};
scanf("%d%d",&n,&m);
int t = n-1;
while(t)
{
if(t&1) mul(a,b,a);
mul(b,b,b);
t>>=1;
}
int res = (a[0][0]%m+m)%m;
printf("%d\n",res);
return 0;
}
3.构造矩阵求解多项式的递推公式
例题1
斐波那契的前n项和
f
1
=
1
,
f
2
=
1
,
f
3
=
2
,
f
4
=
3
,
…
,
f
n
=
f
n
?
1
+
f
n
?
2
f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n?1}+f_{n?2}
f1?=1,f2?=1,f3?=2,f4?=3,…,fn?=fn?1?+fn?2?
现在问题很简单，输入 n 和 m，求
f
n
f_n
fn? 的前
n
n
n 项和
S
n
?
m
o
d
?
m
S_n\ mod\ m
Sn??mod?m。
已知的公式有
f
n
=
f
n
?
1
+
f
n
?
2
f_n = f_{n-1} + f_{n-2}
fn?=fn?1?+fn?2?
S
n
=
f
1
+
f
2
+
.
.
.
+
f
n
S_n = f_1 + f_2 +...+f_n
Sn?=f1?+f2?+...+fn?
其实还可以得到
S
n
=
S
n
?
1
+
f
n
S_n = S_{n-1}+f_n
Sn?=Sn?1?+fn?(高中的等差数列知识)
知道上面三个公式就够了，就可以构造递推公式了
[
f
(
n
+
1
)
f
(
n
)
S
(
n
)
]
=
[
f
(
n
)
f
(
n
?
1
)
S
(
n
?
1
)
]
[
1
1
1
1
0
0
0
0
1
]
\begin{bmatrix} f(n+1)&f(n)&S(n) \end{bmatrix}=\begin{bmatrix} f(n)&f(n-1)&S(n-1) \end{bmatrix}\begin{bmatrix} 1&1&1\\1&0&0\\0&0&1 \end{bmatrix}
[f(n+1)?f(n)?S(n)?]=[f(n)?f(n?1)?S(n?1)?]???110?100?101????
完全是
f
n
f_n
fn?和
S
n
S_n
Sn?递推公式的结合版
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3;
int n,m;
void mul(int a[][N],int b[][N],int t[][N])
{
static int c[N][N];
memset(c,0,sizeof c);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
c[i][j]=(c[i][j]+(ll)a[i][k]*b[k][j]+m)%m;
memcpy(t,c,sizeof c);
}
int main()
{
int a[N][N]={1,0,0};
int b[N][N]={{1,1,1},{1,0,0},{0,0,1}};
scanf("%d%d",&n,&m);
int t = n;
while(t)
{
if(t&1) mul(a,b,a);
mul(b,b,b);
t>>=1;
}
int res = (a[0][2]%m+m)%m;
printf("%d\n",res);
return 0;
}
例题2
f
1
=
f
2
=
0
f_1=f_2=0
f1?=f2?=0
f
n
=
7
f
n
?
1
+
6
f
n
?
2
+
5
n
+
4
?
3
n
f_n = 7f_{n-1}+6f_{n-2}+5n+4*3^n
fn?=7fn?1?+6fn?2?+5n+4?3n
求解
f
n
f_n
fn?
和n相关的有四项且乘方运算无法用矩阵表示，我们考虑用
f
n
,
f
n
?
1
,
n
,
3
n
f_n,f_{n-1},n,3^n
fn?,fn?1?,n,3n构造，但是对n递推时，会出现常数项，那就需要再加上常数项1作为构造项
于是构造
[
f
n
?
f
n
?
1
?
3
n
?
n
?
1
]
[f_n \ f_{n-1}\ 3^n\ n\ 1]
[fn??fn?1??3n?n?1]这个矩阵，以此进行递推构造
最后得到
[
f
(
n
)
f
(
n
?
1
)
3
n
n
1
]
=
[
f
(
n
?
1
)
f
(
n
?
2
)
3
n
?
1
n
?
1
1
]
[
7
1
0
0
0
6
0
0
0
0
12
0
3
0
0
5
0
0
1
0
5
0
0
1
1
]
\begin{bmatrix} f(n)&f(n-1)&3^n&n&1 \end{bmatrix}=\begin{bmatrix} f(n-1)&f(n-2)&3^{n-1}&n-1&1 \end{bmatrix}\begin{bmatrix} 7&1&0&0&0\\6&0&0&0&0\\12&0&3&0&0\\5&0&0&1&0\\5&0&0&1&1 \end{bmatrix}
[f(n)?f(n?1)?3n?n?1?]=[f(n?1)?f(n?2)?3n?1?n?1?1?]???????761255?10000?00300?00011?00001????????
同样矩阵快速幂求解，类似上述代码
例题3
佳佳的斐波那契数列
用 S(n) 表示 Fibonacci 前 n 项和 mod m 的值，即
S
(
n
)
=
(
F
1
+
F
2
+
.
.
.
+
F
n
)
m
o
d
?
m
S(n)=(F_1+F_2+...+F_n) mod\ m
S(n)=(F1?+F2?+...+Fn?)mod?m，其中
F
1
=
F
2
=
1
,
F
i
=
F
i
?
1
+
F
i
?
2
F_1=F_2=1,F_i=F_{i?1}+F_{i?2}
F1?=F2?=1,Fi?=Fi?1?+Fi?2?
用
T
(
n
)
=
(
F
1
+
2
F
2
+
3
F
3
+
.
.
.
+
n
F
n
)
m
o
d
?
m
T(n)=(F_1+2F_2+3F_3+...+nF_n )mod \ m
T(n)=(F1?+2F2?+3F3?+...+nFn?)mod?m 表示 Fibonacci 数列前 n 项变形后的和 mod m 的值。
给定 n 和 m，请求出 T(n) 的值。
T
n
=
F
1
+
2
F
2
+
?
+
n
F
n
=
∑
i
=
1
n
i
F
i
T_n = F_1+2F_2+?+nF_n=\sum _{i=1}^{n}iF_i
Tn?=F1?+2F2?+?+nFn?=∑i=1n?iFi?
T
n
T_n
Tn?变量中含有i,无法构造转移矩阵，只有转移矩阵全是常数才能构造。
所以要对式子进行变换，找到合适的可以变换的式子。
构造新的数列：
Y
n
=
n
S
n
?
T
n
Y_n = nS_n-T_n
Yn?=nSn??Tn?
式①：
n
S
n
?
T
n
=
(
n
?
1
)
F
n
+
.
.
.
+
F
n
?
1
nS_n-T_n=(n-1)F_n+...+F_{n-1}
nSn??Tn?=(n?1)Fn?+...+Fn?1?
式②：
n
S
n
+
1
?
T
n
+
1
=
n
F
1
+
(
n
?
1
)
F
2
+
.
.
.
+
F
n
nS_{n+1}-T_{n+1}=nF_1+(n-1)F_2+...+F_n
nSn+1??Tn+1?=nF1?+(n?1)F2?+...+Fn?
式②-式①：
Y
n
+
1
?
Y
n
=
S
n
Y_{n+1}-Y_n=S_n
Yn+1??Yn?=Sn?
那么就可以构造
[
F
n
+
1
F
n
S
n
Y
n
]
\begin{bmatrix} F_{n+1}&F_n &S_n&Y_n\end{bmatrix}
[Fn+1??Fn??Sn??Yn??]这个递推矩阵
即
[
F
n
+
1
F
n
S
n
Y
n
]
=
[
F
n
F
n
?
1
S
n
?
1
Y
n
?
1
]
[
1
1
1
0
1
0
0
0
0
0
1
1
0
0
0
1
]
\begin{bmatrix} F_{n+1}&F_n &S_n&Y_n\end{bmatrix}=\begin{bmatrix} F_{n}&F_{n-1} &S_{n-1}&Y_{n-1}\end{bmatrix}\begin{bmatrix} 1&1&1&0\\1&0&0&0\\0&0&1&1\\0&0&0&1 \end{bmatrix}
[Fn+1??Fn??Sn??Yn??]=[Fn??Fn?1??Sn?1??Yn?1??]?????1100?1000?1010?0011??????
从
[
1
?
0
?
0
?
0
]
[1 \ 0\ 0\ 0]
[1?0?0?0]开始递推，共有n次方
最后根据
T
n
=
n
S
n
?
Y
n
T_n=nS_n-Y_n
Tn?=nSn??Yn?求出
Y
n
Y_n
Yn?
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 4;
int n,m;
void mul(int a[][N],int b[][N],int c[][N])
{
static int t[N][N];
memset(t,0,sizeof t);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
t[i][j]=(t[i][j]+(ll)a[i][k]*b[k][j]+m)%m;
memcpy(c,t,sizeof t);
}
int main()
{
int a[N][N]={1,0,0,0};
int b[N][N]={{1,1,1,0},{1,0,0,0},{0,0,1,1},{0,0,0,1}};
scanf("%d%d",&n,&m);
int t = n;
while(t)
{
if(t&1) mul(a,b,a);
mul(b,b,b);
t>>=1;
}
ll res = (((ll)n*a[0][2]-a[0][3])%m+m)%m;
printf("%lld\n",res);
return 0;
}
参考链接：
1.矩阵快速幂详解
2.OIWiki矩阵详解
往期优质文章推荐
|