(矩阵)快速幂

快速乘法:

ll qmul(ll x,ll y)
{
    ll res=0;
    for(;y;y>>=1,x<<=1)
        if(y&1)res+=x;
    return res;
}

快速幂:

ll qpow(ll x,ll y)
{
    ll res=1;
    for(;y;y>>=1,x=x*x)
        if(y&1)res=res*x;
    return res;
}

矩阵快速幂:

struct matrix
{
    int n,m;
    ll ma[105][105];
    matrix(int x,int y):n(x),m(y) {clear();}
    void set(int _n,int _m){n=_n,m=_m;}
    ll* operator[](int x){return ma[x];}
    matrix operator*(matrix x)
    {
        assert(m==x.n);
        matrix res(n,x.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=x.m;j++)
                for(int k=1;k<=m;k++)
                    (res[i][j]+=ma[i][k]*x[k][j]%mod+mod)%=mod;
        return res;
    }
    matrix operator^(ll y)
    {
        assert(n==m);
        matrix x(n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                x[i][j]=ma[i][j];
        matrix res(x.n,x.n);
        for(int i=1;i<=x.n;i++)
            res[i][i]=1;
        for(;y;y>>=1,x=x*x)
            if(y&1)res=res*x;
        return res;
    }
    void print()
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                printf("%lld%c",ma[i][j]," \n"[j==m]);
    }
    void clear() {memset(ma,0,sizeof(ma));}
};