我这种小蒟蒻就只能浅谈一下矩阵这种神奇的东西啦。
但正因为是蒟蒻,所以讲的比较好懂(大概)。
本篇分为两部分——>上:矩阵加速递归+下:高斯消元
如果没有你想看的那我深感抱歉...我太弱了只会讲这两个(说不定以后有补充)
——正片开始——
首先,不知道什么是矩阵的这里请:必应
我们用矩阵优化递推一般只需要会矩阵乘法和矩阵加法,矩阵乘法当然用得最多...
既然是浅谈,我就简单讲讲矩阵的这两个基本运算吧。
1. 矩阵加法:
要求:两个矩阵同型(即行列数相同)。然后我们对应位置的元素加起来就好了...
一个N*M的矩阵A加一个N*M的矩阵B会得到一个N*M的矩阵。
2. 矩阵乘法:
要求:两个矩阵中的一个矩阵的列数等于另一个矩阵的行数。
一个N*K的矩阵A和一个K*M的矩阵B相乘会得到一个N*M的矩阵C。
我懒得敲Latex了,自己找去...对于它任意一个元素,值为:
$$C_{i,j}=\sum_{k=1}^{n}a_{i,k}b_{k,j} $$
我这是为了美观...
然后就给段代码吧。
struct Matrix{ int a[N][N]; Matrix(){memset(a,0,sizeof a);} int ln,lm;//长度 Matrix operator *(const Matrix&b)const{ Matrix res;res.ln=ln;res.lm=b.lm; for(int i=1;i<=ln;i++) for(int j=1;j<=b.lm;j++) for(int k=1;k<=lm;k++) res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%MOD; } };
挺简单的吧?那么它有什么用呢?
用处很多。比如:加速递推,加速递推,……(省略10w+字)。
好啦,just a joke,只是我们只讲加速递推。
你可能会想,一般递推都已经O(n)了,你还要加速?
当然了,一些丧心病狂的出题人超喜欢巨型数据。
比如给你个1e9的递推啥的,都是经常的事了。
想到递推,我就想到今年下半年斐波那契数列。
递推式:$\text{f(n)=f(n-1)+f(n-2)}$
咳咳,只是为了美观
然后我们来构造递推矩阵。对了,有件事忘说了。
我们考虑使用矩阵乘法加速递推也是有前提的:
决策点的个数少,数据范围大,线性的递推或类线性的递推(以后会讲)
我们注意到,fib只有两个决策点,于是我们尝试使用二维矩阵,不行就加维呗。
然后我们就构造出来了。(告诉我怎么构造的啊?不说锤爆你狗头)
首先,我们构造一个答案矩阵。(???)
看,就是这个:淦,怎么又要用Latex...
$F(n)= \left|\begin{matrix} f(n) & f(n-1) \end{matrix} \right| $
你可能会疑惑,为什么要这么构造?
实际上,我们希望通过F(n)得到F(n+1)来完成一个递推。
我们知道$F(n+1)= \left|\begin{matrix} f(n+1) & f(n) \end{matrix} \right| $
F(n)包含了f(n)和f(n-1)两个信息,正是我们得到f(n+1)所需要的。
那么我们设F(n)*base=F(n+1)。所以我们希望构造出一个base矩阵来满足它的心愿。
由于F(n)*base=F(n+1),所以我们可以设$base= \left|\begin{matrix} a & b \\ c & d \end{matrix} \right| $
然后我们需要知道a,b,c,d的值。(为什么base是2*2的啊)
(ans矩阵是1*2的,base矩阵得要是2*2的,才能得到1*2的ans矩阵)。
然后我们先把ans和base乘起来再说:
这篇怎么这么多Latex,点个推荐吧,我太难了TuT
$$\left|\begin{matrix} f(n) & f(n-1) \end{matrix} \right| \times \left|\begin{matrix} a & b \\ c & d \end{matrix} \right| = \left|\begin{matrix} af(n)+cf(n-1) & bf(n)+df(n-1))\end{matrix} \right| = \left|\begin{matrix} f(n+1) & f(n) \end{matrix} \right|$$
我们再根据递推式可以得到$base= \left|\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right| $
我们得到了递推矩阵,怎么加速呢?这时我们就要用到强大的快速幂了。
以防有读者不知道快速幂,我这里简单讲解一下,快速幂就是利用二进制划分思想加速幂运算的一个简单算法。
正整数快速幂可以这样写:
ll qpow(int x,int y){ ll tmp=x,con=1; while(y){ if(y&1)con=con*tmp%MOD; tmp=tmp*tmp%MOD; y>>=1; }return con; }
但是这里我们需要矩阵快速幂。
我们简单分析可以得到:$F(n)=F(2) \times base \times base \times ... \times base$,base累乘了n-2次。
为什么是从F(2)开始计算呢?
我们知道$F(2)= \left|\begin{matrix} f(2) & f(1) \end{matrix} \right| $
还知道$F(1)= \left|\begin{matrix} f(1) & f(0) \end{matrix} \right| $,然而我们并不能计算f(0)。
于是我们从F(2)开始计算,矩阵乘法满足结合律,所以我们可以得到最终的结果:
$F(n)= \left|\begin{matrix} f(2) & f(1) \end{matrix} \right| \times \left|\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right|$
至此得解,给出代码:
#include<bits/stdc++.h> using namespace std; long long n; const long long mod=1e9+7; struct Matrix{//封装成结构体更方便食用 long long a[3][3]; Matrix(){memset(a,0,sizeof(a));} Matrix operator *(const Matrix &b)const{ Matrix res; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod; return res; } }ans,base; void init(){//初始化ans和base矩阵 base.a[1][1]=base.a[1][2]=base.a[2][1]=1; ans.a[1][1]=ans.a[1][2]=1; } void qpow(long long b){//矩阵快速幂 while(b){ if(b&1)ans=ans*base; base=base*base; b>>=1; } } int main(){ scanf("%lld",&n); if(n<=2){ puts("1");return 0; } init(); qpow(n-2); printf("%lld",ans.a[1][1]%mod); return 0; }
斐波那契数列算是最基础的矩阵加速递推的例子了,接下来我们来看看更难一点的。
比如说,我们有这样一个递推式:$f(n)=3\times f(n-1)+2\times f(n-2)+f(n-3)+3$
(我为啥要给自己挖这么大一个坑...),这待会儿Latex要写死我
然后我们一起来推一下吧:
首先是答案矩阵!
还是一样,我们设$F(n)=\left| \begin{matrix}f(n) & f(n-1) & f(n-2) & 3\end{matrix} \right|$
记住常数项也需要加一维,那我们的base矩阵是什么样的呢?
推导过程与上面一致,由于要写很长的一个Latex而我又比较懒,所以我就写到纸上了...
于是我们得到了base矩阵:$base= \left|\begin{matrix} a & b & c & d \\ e & f & g & h \\ i & j & k & l \\ m & n & o & p \end{matrix} \right| = \left|\begin{matrix} 3 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{matrix} \right|$
然后我们写出初始答案矩阵,为了避免出现f(0),我们从F(3)开始计算,得到这样一个行向量:
$F(3)=\left| \begin{matrix} f(3) & f(2) & f(1) & 3\end{matrix}$
由于从F(3)开始,所以我们算到F(n)实际上只用累成n-3次base,直接qpow(n-3)。
代码在后面,但是在看代码前先尝试自己改一改上面的代码来实现这个递推。
给出初始项:$f_1={3}, f_2={12}, f_3={45}$,检验项(可以自行检查有没有写对):$f_4={165},f_7={7902},f_{10}={377175} $
如果你写对了并且明白了递推矩阵的推导方法,那么你就学会初级的矩阵加速递推了。
难道还有高级的?Bingo。
记得上面说的吗?类线性递推我们也能用矩阵加速。
关于类线性的矩阵加速递推,我会找一个时间补充,若有想看的朋友可以推荐收藏这篇文章不定期来看看。
下篇会讲矩阵&高斯消元...但是我打算先更几篇网络流的blog。(DP高级篇的中和下先咕着...)