矩阵快速幂题目：http://www.51nod.com/Challenge/Problem.html#problemId=1113

文献：利用矩阵快速幂求斐波那契数列变形：https://blog.csdn.net/flyfish1986/article/details/48014523

利用矩阵快速幂求斐波那契数列变形题目：https://ac.nowcoder.com/acm/contest/17561/B

两大前提:

1.矩阵乘法

2.快速幂

低精度

#include<iostream>
using namespace std;
const int N = 105,mod = 1e9+7;
typedef long long ll;
int n,m;
struct Matrix
{
    int m[N][N];
}unit;
void init()
{
    for(int i=0;i<n;i++)    unit.m[i][i]=1; //初始化为单位矩阵
}
Matrix operator*(Matrix A,Matrix B) //矩阵乘法运算符重载
{
    Matrix res;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ll x=0;
            for(int k=0;k<n;k++)
            {
                x+=(ll)A.m[i][k]*B.m[k][j]%mod; //矩阵乘法
            }
            res.m[i][j]=x%mod;
        }
    }
    return res;
}
Matrix Matrix_qpow(Matrix A,ll k)   //矩阵快速幂
{
    Matrix res=unit;    //初始化为单位矩阵
    while(k)
    {
        if(k&1) res=res*A;
        A=A*A;
        k>>=1;
    }
    return res;
}
int main()
{
    cin>>n>>m;
    Matrix A;
    init();
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>A.m[i][j];
    A=Matrix_qpow(A,m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<A.m[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

不用重载

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
typedef pair<int,int>PII;

const int N = 100 + 5, mod = 1E9 + 7;
typedef long long ll;

int n, m;

struct Matrix{
    ll m[N][N];
}res, in;

Matrix cf(Matrix &A, Matrix &B){
    Matrix t;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            ll x = 0;
            for(int k = 1; k <= n; k ++ ){
                x = (x + A.m[i][k] * B.m[k][j]) % mod;
            }
            t.m[i][j] = x;
        }
    }
    return t;
}

void qpow(Matrix A, int k){
    for(int i = 1; i <= n; i ++ ) res.m[i][i] = 1;
    while(k){
        if(k & 1) res = cf(res, A);
        A = cf(A, A);
        k >>= 1;
    }
}

int main(){
    ios;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            cin >> in.m[i][j];
    qpow(in, m);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ )
            cout << res.m[i][j] << " ";
        cout << '\n';
    }
    return 0;
}

十进制快速幂&&十进制矩阵快速幂

文献：https://blog.csdn.net/weixin_43731933/article/details/98406479?utm_source=app&app_version=4.7.0&code=app_1562916241&uLinkId=usr1mkqgl919blen

高精度

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
int x1,x0,a,b,m;
string s;
struct Matrix
{
    ll m[2][2];
}unit;
void init()
{
    for(int i=0;i<2;i++)    unit.m[i][i]=1;
}
Matrix operator*(Matrix A,Matrix B)
{
    Matrix res;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        {
            res.m[i][j]=0;
            for(int k=0;k<2;k++)
            res.m[i][j]=(res.m[i][j]+A.m[i][k]*B.m[k][j]%m)%m;
        }
    return res;
}
void qpow(ll n)
{
    Matrix res=unit;
    Matrix A;
    A.m[0][0]=a,A.m[0][1]=b,A.m[1][0]=1,A.m[1][1]=0;
    while(n>=0)
    {
        ll cnt=s[n]-'0';
        for(int i=1;i<=cnt;i++) res=res*A;
        Matrix CF[2];
        A=A*A;  //2
        CF[0]=A*A;  //4
        CF[1]=CF[0]*CF[0];    //8
        A=CF[1]*A;
        n--;
    }
    cout<<(res.m[1][0]*x1+res.m[1][1]*x0)%m<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>x0>>x1>>a>>b;
    cin>>s;     //输入几次幂
    cin>>m;     //对m取模题目要求
    init();
    qpow(s.size()-1);
    return 0;
}