【模板】矩阵快速幂

题目

洛谷P3390【模板】矩阵快速幂

题解

矩阵快速幂的原理与普通快速幂相似,关键在于矩阵运算满足乘法结合律。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月14日 下午8:50

【小白解析】
此题解法基本继承一般快速幂解法。
补充说明:quick_pow()方法中的c矩阵(单位矩阵),其意义在于在第25行中,让幂的二进制表示中,该位为1所对应的矩阵幂参与运算。初始时c的主对角线均为1,其余均为0,意在与a相乘时将结果正确地排布在矩阵中,为矩阵运算的基本常识。该点可以自行举例运算证明。