整数的快速幂

int quick_pow(int a,int n){    register int ret=1;    while(n)    {        if(n&1)ret=1LL*ret*a%mod;        a=1LL*a*a%mod;        n>>=1;    }    return ret;}

---

矩阵快速幂

环中做除法：\(\frac{a}{b}\%M=\frac{a\%bM}{b}\)

struct matrix{    int a[100][100],N;    matrix(int x):N(x){memset(a,0,sizeof a);}    int* operator [] (int i){return a[i];}    matrix operator * (matrix & B)    {        matrix ret(N);        for(int i=0;i
    
     >=1;    }    return ret;}