模板 (整数 & 矩阵快速幂) | 洛谷 P1226 & P33

P1226 【模板】快速幂||取余运算

输入输出样例

输入样例#1：
2 10 9

输出样例#1：
2^10 mod 9=7

题目链接：https://www.luogu.org/problemnew/show/P1226

AC代码：

//【快速幂取模】 
//用时: 21ms / 内存: 792KB
#include<iostream>
#include<cstdio>
using namespace std;

// a的b次方对c取模
// 注意类型要用long long
// 取模运算【(a*b)%c == ((a%c)*(b%c))%c】
long long pow_mod(long long a,long long b,long long  c)  
{
    long long ans = 1,base=a;
    base = base % c;
    //【考虑0次方的情况】【坑点，最后一组数据WA】
    // 数据：1^0 % 1；结果：0。
    if(b==0)
    {
        return 1%c;// 任意a的0次幂都是1,故直接用1%c即可 
    } 
    while(b)
    {   
        if(b & 1)ans = (ans*base) % c; 
        b = b >> 1;
        base = (base * base) % c; 
    } 
    return ans;
} 

long long a,b,mod;// 注意类型 
int main()
{
    scanf("%lld%lld%lld",&a,&b,&mod);
    long long result=pow_mod(a,b,mod); 
    printf("%lld^%lld mod %lld=%lld\n",a,b,mod,result);// 注意输出格式
}

P3390 【模板】矩阵快速幂

输入输出样例

输入样例#1：
2 1
1 1
1 1

输出样例#1：
1 1
1 1

题目链接：https://www.luogu.org/problemnew/show/P3390

AC代码：

// 利用快速幂的思想,根据矩阵的结合律,可以递归二分求解
//【矩阵快速幂】 
#include<iostream>
#include<cstdio>
#include<cstring> //包含memset函数
using namespace std;

long long mod=1e9+7;
long long n,k;// 注意类型要为long long，不然全部WA
// 结构体存一个二维数组(矩阵)，可以直接return出来【一点好处】
struct Mat
{
    long long mat[105][105];
};

//输入优化【适用于正负整数】 
inline long long read() 
{ 
    long long X=0,w=0; 
    char ch=0; 
    while(!isdigit(ch)) 
    {
        w|=ch=='-';
        ch=getchar();
    } 
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); 
    return w?-X:X; 
}
// 重载*运算符 
Mat operator*(Mat A,Mat B)
{
    Mat temp;
    //memset(temp.mat,0,sizeof(temp.mat));// 将矩阵置0【零矩阵】 
    for(int i =0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ;j++)
        {
            temp.mat[i][j]=0;// 可以在这里做零矩阵，省一点时间
            for(int k = 0 ;k < n ;k++)
            {
                temp.mat[i][j] = (temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
            }
        }
    }
    return temp;// 返回矩阵A*B的结果 
}
// 重载^运算符 
Mat operator^(Mat A,long long k)//【坑点】这里的k一开始没有long long，导致全部WA 
{
    Mat base;
    // 将矩阵base置为单位矩阵【单位矩阵】 
    // 只需矩阵主对角线的元素为1即可，故可以只要一个循环
    for(int i=0;i<n;i++) base.mat[i][i]=1;

    // 矩阵快速幂【核心代码】 
    while(k)
    {
        if(k&1) base = base * A;
        A = A * A;
        k = k >> 1; 
    }
    return base;
}

int main()
{
    n=read();// 输入优化
    k=read();// 输入优化
    Mat ans;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans.mat[i][j]=read();// 输入优化
        }
    }
    ans=ans^k;// ans^k【矩阵快速幂】 
    // 输出矩阵
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%lld ",ans.mat[i][j]);
        }
        puts("");// 这里是换行，相当于printf("\n");
    }
    return 0;
}

写在最后：

• 再一次看到了二进制的奇妙用法，对比其他的进制数，二进制更加有趣、奇妙。

• 对整数快速幂和矩阵快速幂不熟悉的同学，可以先看看之前关于快速幂的文章。

学习不断，相互鼓励，如有错误，还望指出。