矩阵幂级数

全栈程序员-站长 • 2026年3月19日下午11:45 • 未分类 • 阅读 2

矩阵幂级数题意原题给出矩阵 A 求 A A 2 A k 思路手推一下即可算出 A A 2 A k A A 2 A k 2 A k 2 A A 2 A k 2 二分矩阵快速幂即可注意奇数的时候多加一个 A k 代码 includecstdi includecstdl includecstri includecmath defineGETMOD

题意（原题）：给出矩阵A，求A+A^2…A^k。
思路：手推一下，即可算出A+A^2…A^k = A+A^2…+A^k/2+A^k/2(A+A^2…+A^k/2)。
二分+矩阵快速幂即可。注意奇数的时候多加一个A^k。
代码：

#include 
    #include 
    #include 
    #include 
    #define GETMOD %Mod using namespace std; int n,k,Mod; struct node { int xcnt,ycnt; int a[31][31]; node() { xcnt=n;ycnt=n; memset(a,0,sizeof(a)); } }a; node dw() { node ans; for(int i=1;i<=n;i++)ans.a[i][i]=1; return ans; } node cf(node x,node y) { node ans; for(int i=1;i<=ans.xcnt;i++) for(int j=1;j<=ans.ycnt;j++) for(int k=1;k<=x.ycnt;k++) ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j]GETMOD)GETMOD; return ans; } node jf(node x,node y) { node ans; for(int i=1;i<=x.xcnt;i++) for(int j=1;j<=x.ycnt;j++) ans.a[i][j]=(x.a[i][j]+y.a[i][j])GETMOD; return ans; } node power(int k) { node ans=dw(),x=a; while(k) { if(k%2==1)ans=cf(ans,x); x=cf(x,x); k/=2; } return ans; } node getSum(int x) { if(x==1)return a; node ans,t=getSum(x/2); node y=power(x/2); ans=cf(y,t); ans=jf(t,ans); if(x&1)ans=jf(ans,power(x)); return ans; } int main() { scanf("%d%d%d",&n,&k,&Mod); a.xcnt=n;a.ycnt=n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a.a[i][j]); node ans=getSum(k); for(int i=1;i<=ans.xcnt;i++) { for(int j=1;j<=ans.ycnt;j++) printf("%d ",ans.a[i][j]); printf("\n"); } return 0; }

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/202597.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

微信开发者工具安装教程

上一篇 2026年3月19日下午11:45

浏览器清理缓存快捷键

下一篇 2026年3月19日下午11:46

VS2015 密钥_vs离线激活2015

VS2015 密钥_vs离线激活2015企业版：HM6NR-QXX7C-DFW2Y-8B82K-WTYJV (一般我们都是安装的企业版)专业版：HMGNV-WCYXV-X7G9W-YCX63-B98R2

全栈程序员-站长
2022年8月22日
9
报错Uncaught URIError: URI malformed 可以这样解决

报错Uncaught URIError: URI malformed 可以这样解决最怕写代码出 bug 更怕的是这个 bug 不常见今天把所有的数据都处理完了突然查到一行数据的时候显示了这个问题当时我是一脸懵逼呀 URI url 这个我倒是经常见可是这个 URI 平时不多见呀这是什么原因造成的网上查了一通才发现原来是这样的由于 decodeURI 转码时通过进行解析如果字符串中存在如巴伐利亚黄啤酒精含量 5 0 vol 原麦汁浓度 14 P 原料澳洲大麦芽澳洲焦香麦芽则会出现 URImalformed 就会出现这个问题那么就好解决了解决将字符串中的替换为 25

全栈程序员-站长
2026年3月17日
2
java protostuff 好处_Protostuff详解

java protostuff 好处_Protostuff详解一、Protostuff介绍Protostuff是一个开源的、基于Java语言的序列化库，它内建支持向前向后兼容(模式演进)和验证功能。Protostuff支持的序列化格式包括：protobufprotostuffjsonsmile即二进制json，从protostuff-json模块中使用。Smile数据格式是由JacksonJSON库开发团队于2010年发布的数据格式，并在Jackson1…

全栈程序员-站长
2022年6月7日
31
理解GC

理解GC

全栈程序员-站长
2021年9月7日
63
htc328d屏幕排线怎么换_HTC T328D中文Recovery刷机教程

htc328d屏幕排线怎么换_HTC T328D中文Recovery刷机教程HTCT328D 如何用 Recovery 刷机今天安致小编为大家带来这篇 HTCT328D 中文 Recovery 刷机教程该教程以我们常见的 Recovery 为例对 HTCT328D 刷机进行详细讲解希望对刷机新手有帮助注本文中的 Recovery 只作为参考由于 Recovery 版本多样化可能对应机型与图中不符但刷机的步骤相同 HTCT328D 刷机前的准备 1 检查手机 SD 卡是否存在问题容

全栈程序员-站长
2026年3月20日
2
自然语言处理中的Attention机制总结[通俗易懂]

自然语言处理中的Attention机制总结[通俗易懂]&amp;amp;amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;amp;amp;nbsp;在面试的过程中被问到了attention，原来虽然其实已经实际用过attention了，也知道个大概原理是加权求和，但是对于加权的具体方法以及权值得分的计算并不是很清晰，面试答的一般，正好最近实习的地方

全栈程序员-站长
2022年7月24日
11

发表回复

关注全栈程序员社区公众号