快速幂与矩阵快速幂
2020-01-27 16:00:36来源:博客园 阅读 ()
快速幂与矩阵快速幂
幂运算
幂运算\(a^b\)是\(b\)个\(a\)相乘的结果.
C++自带的幂函数pow
是最朴素的\(O(b)\)算法,效率非常低,所以如果要用到大量幂运算,最好自己打一个快速幂.
快速幂
求\(a^b\%p\)的值.
- 当\(b=1\)时,返回\(a%p\).
- 当\(2\mid b\)时,返回\(pow(a,\frac{b}{2},p)^2%p\).
- 当\(2\nmid b\)时,返回\(pow(a,\frac{b}{2},p)^2%p*a%p\).
时间复杂度为\(O(\log{b})\).
long long poww(long long a,long long b,long long p) {
if(b==1) return a%p;
long long t=1;
t=poww(a,b/2,p);
t=t*t%p;
if(b%2) t=t*a%p;
return t;
}
这样写也行
long long poww(long long a,long long b,long long p) {
long long ans=1;
while(b) {
if(b%2==1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
矩阵乘法
运算方法
矩阵加法,减法,矩阵乘常数这三种运算都很简单,这里不赘述.
有两个分别为\(n\times m\),\(m\times p\)的矩阵\(a,b\)相乘,结果是一个\(n\times p\)的矩阵\(c\).
\(c[i][j]=\sum\limits_{k=1}^{m}{a[i][k]*b[k][j]}\).
代码用结构体实现.
struct mat {
long long (*x)[505]=new long long[505][505];//如果矩阵比较小就直接开数组,太大就用指针.
/*mat() {
memset(x,0,sizeof(x));
}*/ //直接开数组要初始化.
friend mat operator * (mat a,mat b) {//重载
mat c;
for(long long i=1; i<=n; i++) {
for(long long j=1; j<=m; j++) {
for(long long k=1; k<=p; k++) {
c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%MOD)%MOD;
}
}
}
return c;
}
};
时间复杂度为\(O(nmp)\)
常数优化
如果\(a[i][j]=0\),那么会浪费许多时间来计算\(a[i][j]\)与其他数的乘积.
只要改一下循环嵌套的顺序,并判断\(a[i][j]\)是否等于\(0\),如果是就直接continue
.
struct mat {
long long (*x)[505]=new long long[505][505];
friend mat operator * (mat a,mat b) {
mat c;
for(long long k=1; k<=p; k++) {
for(long long i=1; i<=n; i++) {
if(a.x[i][k]==0) continue;//优化
for(long long j=1; j<=m; j++) {
c.x[i][j]=(c.x[i][j]+(a.x[i][k]*b.x[k][j])%MOD)%MOD;
}
}
}
return c;
}
};
矩阵快速幂
其实就是把快速幂中的数换成矩阵.
矩阵快速幂的应用
斐波那锲数列 P1962
这是一个矩阵(\(f(n)\)表示斐波那锲数列第\(n\)项)
\(\left\{ \begin{matrix} f(n-1) \\ f(n-2) \end{matrix} \right\}\)
不难很难发现,只要让它乘上矩阵
\(\left\{ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right\}\)
就能变成\(\left\{ \begin{matrix} f(n) \\ f(n-1) \end{matrix} \right\}\)
所以如果要求\(f(n)\),只需算出\(\left\{ \begin{matrix} f(n-1) \\ f(n-2) \end{matrix} \right\} * \left\{ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right\}^{n-1}\)
结果的第一行第一列就是\(f(n)\).
```cpp
原文链接:https://www.cnblogs.com/gzezfisher/p/pow_matrix.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:快速幂与矩阵快速幂
- 稀疏矩阵类 2020-06-09
- 前缀和 2020-05-04
- 重载矩阵加法运算 代码参考 2020-04-29
- 螺旋矩阵问题 2020-04-18
- 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的 2020-04-15
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash