快速幂模板

C++ 代码

int res=1;//结果置1
while(k)//k为幂次
{
    if(k&1)res*=a;//若k最小位为1，那么说明结果的乘数中含有该项（a）
    k>>=1;//右移一位继续处理次小位
    a*=a;//计算次小位对应的乘数
}
return res;

矩阵幂

C++ 代码

void M_multi(int Matrix_A[][MAXN],int Matrix_B[][MAXN],int n){
    int temp[MAXN][MAXN];
    memset(temp,0,sizeof temp);
    For(i,0,n){
        For(j,0,n){
            For(k,0,n){
                temp[i][j] += Matrix_A[i][k]*Matrix_B[k][j];
            }
        }
    }
    For(i,0,n){
        For(j,0,n){
            Matrix_A[i][j] = temp[i][j];
        }
    }
}
//得到单位阵
void makeE(int n,int ans[][MAXN]){
    For(i,0,n){
        For(j,0,n){
            if(i==j){
                ans[i][j] = 1;
            }
            else{
                ans[i][j]=0;
            }
        }
    }
}
void quickPower(int n,int k,int _ans[][MAXN],int _Matrix[][MAXN]){
    //初始化ans
    makeE(n,_ans);
    while(k){
        if(k&1){
            M_multi(_ans,_Matrix,n);
        }
        M_multi(_Matrix,_Matrix,n);
        k>>=1;
    }
}