矩阵快速幂

科技资讯 投稿 33900 0 评论

矩阵快速幂

by lcx,zjy

基础知识

其实就是二维数组

矩阵加减法

\(A\pm B=C\

\(A[i][j]\与\(B[i][j]\的和或差,即:$ C_{i j}=A_{ij}\pm B_{ij}$

相加减的两个矩阵$ A :B$的行列必须相同

矩阵乘法

\(A\times B=C\

显然两个相乘是要一行和一列对应乘,那么矩阵乘法是需要A的行数B的列数相等的,这是A*B的前提条件

\(\left[ \begin{matrix} a &b \\c &d\\e&f\end{matrix} \right]* \left[ \begin{matrix} g &h&i \\j &k&l\end{matrix} \right]=\left[ \begin{matrix} ag+bj &ah+bk&ai+bl \\cg+dj &ch+dk&ci+dl\\eg+fj&eh+fk&ei+fl\end{matrix} \right]\

$ \left[ \begin{matrix} g &h&i \j &k&l\end{matrix} \right]*\left[ \begin{matrix} a &b \c &d\e&f\end{matrix} \right]=\left[ \begin{matrix} ag+ch+ei &bg+dh+fi\aj+ck+el&bj+dk+fl\end{matrix} \right]$

不满足交换律的

\(C\的行数应该是\(A\的行数,列数应该是\(B\的列数,并且\(C\也是一个方阵(行数和列数相等的矩阵)

代码:

int c[N][N];
void Mul(int a[][N],int b[][N],int n{//n是矩阵大小
    memset(c,0,sizeof(c;
    for(int i=1;i<=n;i++{
        for(int j=1;j<=n;j++{
            for(int k=1;k<=n;k++{
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
}

应用

矩阵快速幂加速递推

矩阵快速幂

矩阵幂就是算$ A^n $

证明:

于是——

$ A = \begin{cases} A, & 当m = 1时 \ (A^{\frac m2}^2, & 当m为偶数时 \ (A^{\frac m2}^2\times A, & 当m为奇数时 \end{cases}$

把快速幂算法中的乘法改成矩阵的乘法就可以了

ans的初始化就相当于普通快速幂需要初始化为1,即乘上这个矩阵值不改变

\(2 \times 2\的矩阵,乘矩阵$ \left[ \begin{matrix} 1 &0 \0 & 1\end{matrix} \right] $值不变,因此可以设其为初始矩阵

ans的初始化就是对角线是1其他全是0

struct node{
    int z[N][N];
};
node mul(node a,node b{//矩阵乘法 
    node ans;
    memset(ans.z,0,sizeof(ans.z;
    for(int i=0;i<N;i++
        for(int j=0;j<N;j++
            for(int k=0;k<N;k++
                ans.z[i][j]=(ans.z[i][j]+a.z[i][k]*b.z[k][j]%mod%mod;
    return ans;
}
node power(int cnt{//快速幂,只不过底数换成了矩阵
    node ans,A;
    memset(ans.z,0,sizeof(ans.z;
    //A一些赋值 
    for(int i=0;i<N;i++ans.z[i][i]=1;//ans的赋值 
    while(cnt{
        if(cnt&1//奇数的话ans*A
            ans=mul(ans,A;
        A=mul(A,A;//A平方
        cnt>>=1;//幂次/2
    }
    return ans;
}

ps:时间复杂度$ O(n^3logm$

先看一个简单的例子:

[POJ3070]Fibonacci

\(F_0\ = 0, \(F_1\=1,和\(F_n\ = \(F_{n−1}\ + \(F_{n−2}\(n≥2.给定整数n\((0≤n≤10^9\,计算\(F_n\.

列解析式:显然:$ F(n=F(n-1+F(n-2$,但这个数据范围就不是很显然了。

建立矩阵递推式,找到转移矩阵:

$F[i]=1*F[i-1]+1 *F[i-2] $

\(F[i-1]=1*F[i-1]+0 *F[i-2]\

\(\left[ \begin{matrix} F_{i-1} &F_{i-2} \end{matrix} \right]*\left[ \begin{matrix} 1 &1 \\1 &0 \end{matrix} \right]=\left[ \begin{matrix} F_i &F_{i-1}\end{matrix} \right]\

我们还可以把上述式子转换一下:

\(( F[i] , F[i-1] =( F[i-1] ,F[i-2] *A=( F[i-2] ,F[i-3] *A *A\

\((F[n] F[n-1]=(F[1] ,F[0] *A^{n-1}\,即:\(F(n=F(1 *A^{n-1}\

于是——

\(1*n\的矩阵,$ A\(是\nn\(的矩阵,则\F'= FA$也是\(1*n\的矩阵

\(F\和\(F'\可以看作是一维数组,省略他们的行下标1,按照矩阵乘法的定义,有:

j=\displaystyle\sum{k=1}^nF_k*A_{kj}$

\(A\,从原始状态\(F\递推到了\(F'\状态:

\(\left[ \begin{matrix} F_1 &F_2 &F_3 \end{matrix} \right]\times \left[ \begin{matrix} A_{11} &A_{12} &A_{13} \\A_{21} &A_{22} &A_{23} \\A_{31} &A_{32} &A_{33}\end{matrix} \right]=\left[ \begin{matrix} F'_1 &F'_2 &F'_3\end{matrix} \right]\
那么如果假设目标状态为\(G\,递推矩阵为\(A\,初始条件为\(F\,则可得出:

\(G=A^n*F\

构造递推矩阵\(A\

Fibonacci前n项和

Fibonacci数列,f[1]=1,f[2]=1,f[n]=f[n-1]+f[n-2],(\(n>2\,输入n和m,求前n项和模m的值。(\(1\leq n\leq 2\times 10^{9}\,\(1\leq m\leq 1\times 10^9+10\

\(表示前\ \ n $项和,可推出:

\ f[n-1]\f[n+1]=0\ s[n-1]+1f[n]+1\ f[n-1]\f[n]=0 \ s[n-1]+1\ f[n]+0*\ f[n-1] $

$[\ s[n]\ f[n+1]\ f[n]\ ]=[s[n-1]\ f[n]\ f[n-1]\ ]*\left[ \begin{matrix} 1 & 0 & 0 \1 & 1 & 1\0 &1 & 0 \end{matrix} \right] $

[POJ3734]方块涂色

N个方块排成一列 用红,蓝,绿,黄4种颜色去涂色,求红色方块 和绿色方块个数同时为偶数的 方案数 对10007取余

列解析式:

$ a[i]\(表示从1~i的方块中,红、绿方块数量都是偶数的方案数 \b[i]\(表示从1~i的方块中,红、绿方块数量一个是偶数一个是奇数的方案数 \c[i]$表示从1~i的方块中,红、绿方块数量都是奇数的方案数
初始:a(0=1; b(0=0; c(0=0

1.到i时红和绿的方格个数都是偶数,且i+1个方块被染成了蓝或黄色

且i+1个方块被染成了奇数个所对应的颜色

\(a[i+1]=2*a[i]+b[i]\

\(b[i+1]=2*a[i]+2*b[i]+2*c[i]\
\(c[i+1]=b[i]+2*c[i]\

建立矩阵递推式,找到转移矩阵:

$\left[ \begin{matrix} a_i&b_i&c_i\end{matrix} \right] *\left[ \begin{matrix} 2&2&0 \1&2&1\0 &2& 2 \end{matrix} \right]=\left[ \begin{matrix} a_{i+1}&b_{i+1}&c_{i+1}\end{matrix} \right] $

矩阵快速幂加速递推题目特点:

状态矩阵),矩阵在单位时间内变化一次

3.递推轮数大,但矩阵长度n不大

构建矩阵递推的大致套路:

\(就叫做**转移矩阵**,它能把\ F[n-1] \(转移到\ F[n] \(;然后这就是个等比数列,直接写出通项\ F[n]=A^{n-1}*F[1]\(此处\ f[1] $叫初始矩阵。

一般$ F[n]\(与\F[n-1] \(都是按照原始递推式来构建的,当然可以先猜一个\ F[n] $。

\(,\T $是递归总轮数


矩阵表示修改

[THUSCH2017] 大魔法师

\(A\ \(B\ \(C\。有m次操作,每次操作选择一个区间\([l,r]\进行一下七种操作之一:

\(A_i=A_i+B_i\

\(B_i=B_i+C_i\

\(C_i=C_i+A_i\

\(A_i=A_i+v\

\(B_i=B_i\times v\

\(C_i=v\

\(\displaystyle\sum_{i=l}^rA_i\,\(\displaystyle\sum_{i=l}^rB_i\,\(\displaystyle\sum_{i=l}^rC_i\

于是就想矩阵乘法来改变状态:

\(1\times 4\的矩阵\([A,B,C,1]\(最后一个\(1\用来维护常项)

1.\([A,B,C,1]\times \begin{bmatrix} 1 & 0&0&0 \\ 1 & 1&0&0\\0&0&1&0\\0&0&0&1 \end{bmatrix}=[A+B,B,C,1]\

4.\([A,B,C,1]\times \begin{bmatrix} 1 & 0&0&0 \\ 0 & 1&0&0\\0&0&1&0\\v&0&0&1 \end{bmatrix}=[A+v,B,C,1]\

\([A,B,C,1]\times \begin{bmatrix} 1 & 0&0&0 \\ 0 & v&0&0\\0&0&1&0\\0&0&0&1 \end{bmatrix}=[A,B*v,C,1]\

\([A,B,C,1]\times \begin{bmatrix} 1 & 0&0&0 \\ 0 & 1&0&0\\0&0&0&0\\0&0&v&1 \end{bmatrix}=[A,B,v,1]\

\([l,r]\中的数据,那就把这段区间全部都乘一个\(\begin{bmatrix} 1 & 0&0&0 \\ 1 & 1&0&0\\0&0&1&0\\0&0&0&1 \end{bmatrix}\就好了,于是就可以用线段树来维护了

[BZOJ2973]石头游戏

\(n\行\(m\\((0\leq n,m\leq 8\的矩阵,还有一个与之对应的\(n\\(m\列操作序列,一共有\(act\种操作序列,编号\(0到(act-1)\\((0\leq act\leq10\每一种操作序列都是长度不超过6,循环执行,一秒一个,所有格子同时进行包括:

NWSE:把这个格子内所有的石头推到相邻的格子,N表示上方,W表示左方,S表示下方,E表示右方

问t秒\((1\leq t\leq10^9\之后,所有方格中石头最多的格子有多少个石头

以样例为例,设定一维矩阵\(F_t=[a_1\ a_2\ a_3\ a_4\ a_5\ a_6]\表示\(t\秒时当前每个格子的石子数量,特别的,再加一个\(a_0\,使得\(a_0\始终为\(1\,所以,转移矩阵\(T_i\\(0\列有且只有第\(0\行为\(1\

\(F_0=[a_0=1\ a_1=0\ a_2=0\ a_3=0\ a_4=0\ a_5=0\ a_6=0]\

\(1,E,E,E,E,0\,第1个格子+1,第2,3,4,5个格子推向右方,第6个格子不移动不添加

\(T_1=\begin{bmatrix} 1 & 1&0&0&0&0&0 \\ 0 & 1&0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1 \\0&0&0&0&0&0&1 \end{bmatrix}\

\(T_2\、\(T_3\\(T_4\\(T_5\...

\(n\和\(m\的数据范围较小,所以我们可以把\(n\\(m\列的网络转化为长度为\(n\times m\的一维矩阵

\(F_t=[a_{(1,1},a_{(1,2}...a_{(1,m},a_{(2,1}...a_{(n,m}]\,其中\(a_{(i,j}\在一维矩阵第\((i-1\times m+j\个位置,令\(S(i,j=(i-1\times m+j\,也再加一个$ a_0$,始终为\(1\

\(6\,且\(1-6\的最小公倍数为\(60\,所以每经过\(60\秒,操作序列又会从最开始的字符开始,因此需要构造\(60\\((n\times m+1\times (n\times m+1\转移矩阵\(T\,包含第\(0-(n\times m\行和第\(0-(n\times m\

\(T_i(1\leq i\leq 60\的构造方法:

\(F_i\所有元素与转移矩阵\(T_{i+1}\\(i\列所有元素分别相乘的和,得到状态矩阵\(F_{i+1}\\(i\个元素的数值

若操作数字为\(0-9\,设数值为\(x\,所以\(T_i\\(S(i,j\\(0\\(x\,第\(S(i,j\\(S(i,j\\(1\

\(N\,则转移矩阵第\(S(i,j\\(S(i-1,j\\(1\,字符\(W,S,E\类似

\(D\,则转移矩阵此列不做处理

\(F_i(0\始终为\(1\,所有转移矩阵\(T_i\\(0\列有且只有第\(0\行为\(1\

\(T_1-T_{60}\全部求解出来,令\(TT=T_1\times T_2\times ...\times T_{60}\

\(t\秒后:

\(F_t=F_0*TT^{\frac{t}{60}}*(T_1\times T_2\times ...\times T_r,r=t\%60\

\(TT^{\frac{t}{60}}\可以用矩阵快速幂求解,最后求\(F_t\\(1-(n\times m\列的最大值即可

如果在应用矩阵乘法时,遇到常数项,经常需要在“状态矩阵”中添加一个额外的位置,始终储存常数\(1\,并乘上“转移矩阵”中适当的系数,累加到“状态矩阵”的其他位置


矩阵乘法与邻接矩阵

[TJOI2017]可乐

加里敦星球的人们特别喜欢喝可乐。因而,他们的敌对星球研发出了一个可乐机器人,并且放在了加里敦星球的\(1\号城市上。这个可乐机器人有三种行为: 停在原地,去下一个相邻的城市,自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图,在第\(0\秒时可乐机器人在\(1\号城市,问经过了\(t\秒,可乐机器人的行为方案数是多少?

\(N\表示城市个数,\(M\表示道路个数。

$ 1 < t \leq 10^6, $ \(1≤N≤30,0<M<100,1 \leq u, v \leq N\

先用邻接矩阵存图(两个点之间若有边则\(A[u][v]=1\

令该图的邻接矩阵是\(G\,那么我们考虑 \(G^2\ 是个什么东西

\(G′\ 为相乘得到的矩阵,那么会有

{a,b}=\displaystyle \sum^m{i=1} G_{a,i}*G_{i,b}$

\(G{i,b}\ 都不为零,即\(i\点可连通 \(a,b\ 两点的时候上式的该项才为\(1\, 否则为\(0\

\(a\到\(b\长度为\(2\的路径条数(即方案数

\(G^2\得到的矩阵其实表示了任意两点间长度为2的方案数

\(floyd\算法的角度考虑)那么不难发现\(G^k\的第\(i\行第\(j\列的数字含义是从\(i\\(j\经过\(k\步的路径方案总数

在原地停留很简单,我们只要认为每个点都有一个从自己到自己的自环即可。

我们可以将自爆这个状态也看成一个城市,就设它为编号\(0\

这样就满足了任何一个点随时可以自爆,且无法恢复到其他状态。

\(Ans=\sum\limits_{i=0}^{n}A[1][i]\

编程笔记 » 矩阵快速幂

赞同 (41) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽