矩阵乘法 矩阵快速幂_菜鸡互啄

int mod;
struct matrix
{
    long long a[102][102];//根据实际数据局范围调整。
    int r;
    int c;

    matrix mul (matrix x,matrix y)//矩阵相乘
    {
        matrix t;
        t.r=x.r;
        t.c=y.c;
        for(int i=0; i<x.r; ++i)
            for(int j=0; j<y.c; ++j)
            {
                t.a[i][j]=0;
                for(int k=0; k<y.r; ++k)
                    t.a[i][j]=(t.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
            }
        return t;
    }

    matrix pow (matrix x,int y)
    {
        matrix t=x;//快速幂肯定是方阵，x.r==x.c。所以直接让t=x，再将t中数组a转化成一个单位矩阵。
        memset(t.a,0,sizeof(t.a));
        for(int i=0; i<x.r; ++i) t.a[i][i] = 1;
        while(y)//跟快速幂原理相同
        {
            if(y&1)
                t=mul(t,x);
            y/=2;
            x=mul(x,x);
        }
        return t;
    }

};

int mod;
struct matrix
{
    long long a