这里先引入一个快速幂
正常我们计算 x^22次方的话，要怎么去计算，暴力的话平方22次，这里想一个简单的方法，x^22要怎么计算出来， x^22 = x^16 * x^4 * x^2，折几个数怎么来的呢 ？ 将22转换为 2进制的数 10110 ，正好不就是2^4 = 16, 2^2 = 4, 2^1 = 2 ;
快速幂取模
#define ll long long
ll mod_pow(ll x, ll n, ll mod){
ll res = 1;
while(n > 0){
if (n & 1) res = res * x % mod;
x = x * x % mod;
n >> 1;
}
return res;
}
矩阵快速幂
1 . 矩阵的定义
用一个结构体去定义矩阵
struct mat
{
int a[2][2];
};
2 . 矩阵相乘
学过线代这个就很容易了么，用A矩阵的每一行去乘以B矩阵的每一列，得到一个新的元素。
代码 ：
struct mat
{
int a[2][2];
};
mat mul(mat a, mat b){ // 以2介矩阵为例
mat r;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
r.a[i][j] += (a.a[i][k]*b.a[k][j]) % mod;
r.a[i][j] %= mod;
}
}
}
return r;
}
3 . 矩阵快速幂
mat pow(mat A){
mat B; // 定义出一个单位矩阵
for(int i = 0; i < 2; i++){ //初始化
for(int j = 0; j < 2; j++){
if (i == j) B.a[i][j] = 1;
else B.a[i][j] = 0;
}
}
while(n){
if (n & 1) B = mul(A, B);
A = mul(A, A);
n >>= 1;
}
return B;
}
原文：http://www.cnblogs.com/ccut-ry/p/7818809.html