矩阵快速幂模板

struct M
{
    LL a[3][3];
    void init1()//化单位矩阵
    {
        memset(a, 0, sizeof(a));
        a[0][0]=1;
        a[1][1]=1;
        a[2][2]=1;
    }
    void init0()//清空矩阵
    {
       memset(a, 0, sizeof(a));
    }
};
M mul (M a,M b)
{
    M ans;
    for (int i=0; i<maxn; i++)
    {
        for (int j=0; j<maxn; j++)
        {
            ans.a[i][j]=0;
            for (int k=0; k<maxx; k++)
            {
                ans.a[i][j]+=a.a[i][k]*b.a[k][j];
                ans.a[i][j]%=mod;
            }
        }
    }
    return ans;
}
M qpow(M a,LL n)//快速幂部分
{
    M ans;
    ans.init();
    //这里也可以初始化我要b*a^n中的b矩阵
    while(n)
    {
        if (n&1)ans=mul(ans,a);
        a=mul(a,a);
        n/=2;
    }
    return ans;
}
void output(M a)//随时打印判断
{
    for(int i=0; i<3; ++i)
    {
        for(int j=0; j<3; ++j)
        {
            cout << a.a[i][j] << " ";
        }
        cout << endl;
    }
}