【模板】矩阵快速幂

Andy1101 · 2025-05-24 19:42:34 · 算法·理论

矩阵快速幂

#include <bits/stdc++.h>
using namespace std;
const int P=1e9+7; 
struct Matrix{
    int R,C;
    vector<vector<long long>> a;
    Matrix()
    {
        R=C=0;
    }
    Matrix(int r,int c)
    {
        R=r,C=c;
        a=vector<vector<long long>>(r,vector<long long>(c));
    }
    Matrix(vector<vector<long long>> v)
    {
        R=v.size();
        C=v[0].size();
        a=v; 
    }
    void print()
    {
        for(auto v:a)
        {
            for(auto x:v)
            {
                cout <<(x+P)%P<<" ";
            }
            cout <<'\n';
        }
    }
};
Matrix operator * (const Matrix &A,const Matrix &B)
{
    Matrix D(A.R , B.C);
    for(int i=0;i<D.R;i++)
    {
        for(int j=0;j<D.C;j++)
        {
            for(int k=0;k<B.R;k++)
            {
                D.a[i][j]=(D.a[i][j] + A.a[i][k] * B.a[k][j])%P;
            }
        }
    }
    return D;
}
Matrix operator ^ (const Matrix &A,long long n)
{
    Matrix X=A;
    Matrix ans(A.R,A.C);
    for(int i=0;i<A.R;i++) ans.a[i][i]=1;
    while(n)
    {
        if(n&1) ans=ans*X;
        X=X*X;
        n>>=1; 
    }
    return ans;
}
int main()
{

    return 0;
}