矩阵快速幂



矩阵相乘：

A,B两矩阵相乘得到的新矩阵的第i行j列值为A矩阵的第i行每个元素跟B矩阵第j列每个

元素相乘的和。

需要把主对角线赋值成1其余部分为0来初始化单位矩阵.

快速幂：

求a的b次幂O（lgn）方法（二进制迭代）。

把b转换成2进制数 该2进制数第i位的权为a^（2^(i-1)）

如 a^13=a^(2^0+2^2+2^3)

13的二进制是    1          1         0        1

              2^3*1  +  2^2*1  +  2^1*0  +  2^0*1   =  13  

          

用&1来判断末位是否为0 用>>来将计算过的二进制末位去除

const int mod;

int lm(int a,int b)
{
    int ans=1;
    a%=mod;
    while(b>0)
    {
        if(b&1)
        ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}