快速幂，矩阵快速幂

ll _power(ll a, int b, int p) { //计算(a^b)%p;
ll ans = 1;
while (b) {
if (b & 1) //等价于b%2，判断b的奇偶性
ans = ans * a % p; //如果为奇数，证明该位为1，需要乘上a
a = a * a % p; //计算a^(2^i)
b >>= 1; //等价于b/=2;
}
return ans;
}

struct Mat {
ll m[maxn][maxn];
}ans, a; //ans为结果矩阵，a为输入矩阵
Mat Mul(Mat a, Mat b, int n) {//计算矩阵a乘矩阵b，n为矩阵的大小
Mat c;//临时矩阵c
memset(c.m, 0, sizeof(c.m));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
c.m[i][j] = (c.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
return c;
}
Mat _power(Mat a, int b, int n) {//计算a^b，n为矩阵的大小
for (int i = 1; i <= n; i++)//构造单位矩阵
ans.m[i][i] = 1;
while (b) {
if (b & 1)
ans = Mul(ans, a, n);
a = Mul(a, a, n);
b >>= 1;
}
return ans;
}

快速幂，矩阵快速幂

原文：https://www.cnblogs.com/Kiana-/p/12263450.html