矩阵乘法回顾

目录
经典例题总结


经典例题


网上有什么十大经典例题,但无非3种操作:矩阵的基础运算(例一+加减乘+阶乘),找辅助矩阵解题,与其他知识点结合用作矩阵加速(降复杂度,一般降成logn)


操作一:单单矩阵的基础操作

给定n个点,m个操作,构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转,置换

有些模拟题也会用到矩阵的基础操作,但很少这种矩阵运算。

矩阵乘法回顾

高阶操作:反复置换,共轭转置,酉矩阵,(半)正定矩阵等等
上述定义


操作二 :阶乘

给定矩阵A,请快速计算出A^n(n个A相乘)的结果,输出的每个数都mod p。
给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值

变式:用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案,M<=5,N<2^31,输出答案mod p的结果。

这种题本质上还是一样的,利用状态转换,画个有向图,然后跟上面的问题一样了。
例题:规定宽度为4,给定长度为n,求用12和21的瓷砖,将其完全铺满能有多少种方法。(链接一,还有杜教BM)
链接二,有推导过程

例如 :二阶矩阵如下

const int N=2;
typedef struct matrix{ int a[N][N]; }mt;
mt muti(mt x,mt y){
mt z; memset(z.a,0,sizeof(z.a));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
z.a[i][j]=(z.a[i][j]+x.a[i][j]*y.a[j][k]%mod)%mod;
return z;
}
mt qpow(mt x,int k){
mt y; memset(y.a,0,sizeof(y.a));
for(int i=0;i<N;i++) y.a[i][i]=1;
while(k){
if(k&1) y=muti(y,x);
k>>=1; x=muti(x,x);
}
return y;
}

一个nm的矩阵乘一个mp的矩阵会得到一个n*p的矩阵

//n*m的矩阵乘 m*p的矩阵
typedef struct matrix{ int n,m,a[maxn][maxn]; }mt;
mt muti(mt x,mt y,int n,int m,int p){
mt z; memset(z.a,0,sizeof(z.a));
for(int i=0;i<x.m;i++) //m
for(int j=0;j<y.n;j++) //p
for(int k=0;k<x.n;k++) //n
z.a[i][j]=(z.a[i][j]+x.a[i][j]*y.a[j][k]%mod)%mod;
return z;
}


操作三 :找辅助矩阵
1、专业点说是:用矩阵乘法优化的线性齐次递推公式求值。
2、线性关系推不出的话,可以尝试杜教BM,暴力推出系数,如果推不出,应该不是线性关系。(小编还不会杜教BM)
3、这类题有时也可以用二分,dfs+剪枝,dp等等做。


题型:

1、给定n和p,求第n个Fibonacci数mod p的值,n不超过2^31
普通的有两种方法:详解

往往是变式题,要自己找辅助矩阵
对于f(n)=af(n-1)+bf(n-2)这种递推公式。有一种方法是提特征根方程:讲解
但上面的方法对于特征根是无理数时,无效,无特征根时又要考虑其是否有周期性。而用矩阵乘法写的普适性更强。

找辅助矩阵练习:
一:求Fibonacci前n项和
矩阵递推式;
Sn = 1 * Sn-1 + 1 * fn + 0 * fn-1;
fn+1 = 0 * Sn-1 + 1 * fn + 1 * fn-1;
fn = 0 * Sn-1 + 1 * fn + 0 * fn-1;
{1 1 0}
{0 1 1}
{0 1 0}

二:求Tn= ∑k*fk mod m;

原式
f[i] = f[i-1]+f[i-2]
T[n] = f[1]+f[2]*2+f[3]*3+...+f[n]*n


S[n] = f[1]+f[2]+f[3]+...+f[n]
n*S[n] = n*f[1]+n*f[2]+n*f[3]+...+n*f[n]

--> P[n] = n*S[n]-T[n]
--> P[n] = (n-1)*f[1]+(n-2)*f[2]+...+(n-n)*f[n]
因为
--> P[n-1] = (n-1)*S[n]-T[n-1]
--> P[n-1] = (n-2)*f[1]+(n-3)*f[2]+...+(n-1-(n-1))*f[n-1]

--> S[n-1] = f[1]+f[2]+f[3]+....+f[n-1]
所以
P[n]=P[n-1]+S[n-1]

P[n]=1*P[n-1]+1*S[n-1]+0*f[n]+0*f[n-1];
S[n]=0*P[n-1]+1*S[n-1]+1*f[n]+0*f[n-1];
f[n+1]=0*P[n-1]+0*S[n-1]+1*f[n]+1*f[n-1];
f[n]=0*P[n-1]+0*S[n-1]+1*f[n]+0*f[n-1];

P[i] S[i] f[i] f[i-1]

{1 1 0 0}
{0 1 1 0}
{0 0 1 1}
{0 0 1 0}

最后 T[n] = n*S[n]-P[n];

2、二分递归或找辅助矩阵
题目大意:给定矩阵A,求A + A^2 + A^3 + … + A^k的结果(两个矩阵相加就是对应位置分别相加)。输出的数据mod m。k<=10^9。
一共有4种解法,归于两大种,年代已久,链接已失(其实是懒得再找了)。

3、求下列函数的整数部分(含根号)矩阵乘法回顾

推导过程:矩阵快速幂+共轭复数

然后是通用公式,求整数部分矩阵乘法回顾
注意这类都有一个大前提才能共轭构造,见推导过程



总结

还在刷题,这篇还在更新,没什么好总结的。

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

矩阵乘法回顾

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 矩阵乘法回顾
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏