快速幂/矩阵快速幂

快速幂:

int pow_mod(int a,int b,int c)
{
    a=a%c;
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}

快速乘法:

ll q_mul(ll a,ll b)//计算a*b%mod的值
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%mod;
        }
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}

矩阵快速幂模板:

const int N=2;
struct Matrix
{
    int a[N][N];
    Matrix()
    {
        mem(a,0);
    }
    void init()
    {
        mem(a,0);
        for(int i=0; i<N; i++)
            a[i][i]=1;
    }
};
void print(Matrix a)
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
            printf("%d ",a.a[i][j]);
        puts("");
    }
}
Matrix mul(Matrix a,Matrix b)
{
    Matrix ans;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<N; k++)
            {
                ans.a[i][j]+=a.a[i][k]*b.a[k][j];
                ans.a[i][j]%=mod;
            }
    return ans;
}
Matrix mat_pow(Matrix a,int n)
{
    Matrix ans;
    ans.init();
    while(n)
    {
        if(n&1)
            ans=mul(ans,a);
        a=mul(a,a);
        n>>=1;
    }
    return ans;
}

对于稀疏矩阵:

还有一个对于稀疏矩阵的加速办法……一般矩阵乘法这么写的：
for(int i=0; i<N; i++)
    for(int j=0; j<N; j++)
        for(int k=0; k<N; k++)
            a[i][j]+=b[i][k]*c[k][j];
改成
for(int i=0; i<N; i++)
    for(int j=0; j<N; j++)
        if(b[i][j])
            for(int k=0; k<N; k++)
                a[i][k]+=b[i][j]*c[j][k];