快速幂

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//快速求a^b mod k
ll qmi(ll a, ll b, ll p)
{
    ll res = 1%p;
    while(b)            //b 一定可以表示为 2^a1 + 2^a2 +.....+ 2^at
    {                   //如 6 = 2^1 + 2^2 = 110  ,每个数都有其二进制表示方式
        if(b&1) res = res *a %p;
        a = a*a%p;
        b>>=1;
    }
    return res;

}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        ll a, b, k;

        scanf("%lld%lld%lld",&a, &b, &k);

        printf("%lld\n", qmi(a,b,k));
    }

    return 0;
}

矩阵快速幂

#include<bits/stdc++.h>

using namespace std;

const int N = 3;
int n, mod;
typedef long long ll;

struct mat{ // c++ 中函数的返回值不能为数组，但是struct可以
    ll m[N][N];
}unit; //unit为单位矩阵

void init_unit()  //初始化unit为单位矩阵
{
    for(int i=0; i<N; i++)
        unit.m[i][i] = 1;
}
//适用于两个n*n矩阵的乘法
mat operator *(const mat &x, const mat &y)
{
    mat ans; // 因为此处的ans数组没有初始化为零,所以不能用它去加
    ll t;

    for(int i=0; i<N; i++) // 枚举x矩阵的行(左行)
        for(int j=0; j<N; j++) // 枚举y矩阵的列(右列)
        { 
            t = 0; //存放乘积后求和的结果
            for(int k=0; k<N; k++)
            {
                t += x.m[i][k] * y.m[k][j] % mod;
            }
            ans.m[i][j] = t % mod;

        }

    return ans;
}
//矩阵快速幂 ，计算矩阵a^k %(mod)
mat mat_qmi(mat a, ll k)
{
    mat res = unit; //res为单位矩阵

    while(k)
    { 
        if(k&1) res = res * a; // 记住这里千万不能缩写成res *= a;

        a = a * a;

        k >>= 1;

    }

    return res;
}

int main ()
{
    ll k;   
    cin >> n >> k;
    init_unit();
    mat a;
    for(int i = 0 ; i < n ; i ++ )
        for(int j = 0 ; j < n ; j ++ )
            cin >> a.m[i][j];

    a = mat_qmi(a, k);

    for(int i = 0 ; i < n ; i ++ )
        for(int j = 0 ; j < n ; j ++ )
            if(j == n - 1) cout << a.m[i][j] << endl;
            else cout << a.m[i][j] << ' ';

    return 0;
}