快速幂/矩阵快速幂 模板

注意: 矩阵快速幂把一个二维数组(方阵)放在了struct中，快速幂只适用于方阵size较小的情况，如果size过大的话，main中的栈会溢出，并且由于一次矩阵乘法复杂度是O(n3),很容易超时。
对于一些特别的题，如循环矩阵的话，可以只保留第一行这样就会快很多
例题:https://ac.nowcoder.com/acm/contest/7079/D
题解:https://ac.nowcoder.com/discuss/492088?type=101&order=time&pos=&page=1&channel=666&source_id=search_acm_post

### 快速幂:
###blog:https://blog.csdn.net/qq_44266648/article/details/97500679

代码块
int poww(ll a, ll b, ll mod)
{
    ll ans = 1;
    ll base = a % mod;
    while (b)
    {
        if (b & 1 != 0)
            ans = ans * base % mod;
        b = b >> 1;
        base = base * base % mod;
    }
    return ans;
}

矩阵快速幂:

blog:https://blog.csdn.net/qq_41021816/article/details/82760216

代码块
const int N=9;
struct Matrix{///矩阵结构体 
    ll matrix[N][N];
};

const int mod = 1e9 + 7;

void init(Matrix &res)///初始化为单位矩阵 
{
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i=0;i<N;i++)
        res.matrix[i][i]=1;
}
Matrix multiplicative(Matrix a,Matrix b)///矩阵乘法
{
    Matrix res;
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            for(int k = 0 ; k < N ; k++){
                res.matrix[i][j] += a.matrix[i][k]*b.matrix[k][j];
                res.matrix[i][j] %= mod;
            }
        }
    }
    return res;
}
Matrix Pow(Matrix mx,ll m)///矩阵快速幂 
{
    Matrix res,base=mx;
    init(res);
    while(m)
    {
        if(m&1)
            res=multiplicative(res,base);
        base=multiplicative(base,base);
        m>>=1;
    }
    return res;
}