[矩阵快速幂]

大概就是一个 n*n 的矩阵A 求 A^k 的矩阵。

按照快速幂的思想来写。

void mult(ll a[][110],ll b[][110])
{
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
            {
                tmp[i][j]+=(a[i][k]%mod)*(b[k][j]%mod);
                tmp[i][j]%=mod;
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=tmp[i][j]%mod;
}

void pow(ll a[][110])
{
    memset(res,0,sizeof(res));
    for(int i=1;i<=n;i++)
        res[i][i]=1;
    while(k)
    {
        if(k%2==1) mult(res,a);
        mult(a,a);
        k>>=1;
    }
}