快速幂与矩阵快速幂

0
10

幂运算

幂运算\(a^b\)是\(b\)个\(a\)相乘的结果.
C++自带的幂函数pow是最朴素的\(O(b)\)算法,效率非常低,所以如果要用到大量幂运算,最好自己打一个快速幂.

快速幂

求\(a^b\%p\)的值.

  1. 当\(b=1\)时,返回\(a%p\).
  2. 当\(2\mid b\)时,返回\(pow(a,\frac{b}{2},p)^2%p\).
  3. 当\(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]}\).
矩阵乘法.gif
代码用结构体实现.

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)\).

<

发布回复

请输入评论!
请输入你的名字