矩阵类

改编自范神:ACM-ICPC-Template/模板/9_数学/5_矩阵类.cpp

Tips

请注意unit()方法,该方法返回值为一个单位矩阵

模版

typedef long long mytype;
const int SZ=105;
const long long mod=1000000007;
long long quickpow(long long a, long long b)
{
    if(b < 0) return 0;
    long long ret = 1;
    a %= mod;
    for (; b; b >>= 1, a = (a * a) % mod)
        if (b & 1)
            ret = (ret * a) % mod;
    return ret;
}
long long inv(long long a)
{
    return quickpow(a,mod-2);
}
struct mat
{
    int n,m;
    mytype a[SZ][SZ];

    //构造函数 n行m列
    mat(int n=SZ,int m=SZ):n(n),m(m) {}

    // 初始化
    void init(); //清零
    mat unit(); //该函数的返回值为一个单位矩阵

    // 输入输出
    void in();
    void out();

    //基本运算
    mytype *operator [](int n);
    mat operator +(const mat &b);
    mat operator -(const mat &b);
    mat operator *(const mat &b);
    mat operator *(const mytype &b);
    mat operator /(const mytype &b);
    mat operator !();   //矩阵的转置

    //矩阵快速幂
    friend mat quickpow(mat a, mytype b);
};
void mat::init()
{
    memset(a,0,sizeof(a));
}
mat mat::unit()
{
    mat t(n,n);
    t.init();
    for (int i=0; i<n; i++)
        t.a[i][i]=1;
    return t;
}
void mat::in()
{
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            scanf("%lld",&a[i][j]);
}
void mat::out()
{
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            printf("%lld%c",a[i][j]," \n"[j==m-1]);
}
mytype *mat::operator [](int n)
{
    return *(a+n);
}
mat mat::operator +(const mat &b)
{
    mat t(n,m);
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            t.a[i][j]=(a[i][j]+b.a[i][j]+mod)%mod;
    return t;
}
mat mat::operator -(const mat &b)
{
    mat t(n,m);
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            t.a[i][j]=(a[i][j]-b.a[i][j]+mod)%mod;
    return t;
}
mat mat::operator *(const mat &b)
{
    mat t(n,b.m);
    for(int i=0; i<n; i++)
        for(int j=0; j<b.m; j++)
        {
            t.a[i][j]=0;
            for(int k=0; k<m; k++)
                t.a[i][j]=(t.a[i][j]+(a[i][k]*b.a[k][j])%mod)%mod;
        }
    return t;
}
mat mat::operator *(const mytype &b)
{
    mat t(n,m);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            t.a[i][j]=a[i][j]*b%mod;
    return t;
}
mat mat::operator /(const mytype &b)
{
    mat t(n,m);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            t.a[i][j]=a[i][j]*inv(b)%mod;
    return t;
}
mat mat::operator !()
{
    mat t(m,n);
    for(int i=0; i<m; i++)
        for(int j=0; j<n; j++)
            t.a[i][j]=a[j][i];
    return t;
}

mat quickpow(mat a, mytype b)
{
    if(b<0) return a.unit();
    mat ret=a.unit();
    for (; b; b>>=1,a=a*a)
        if (b&1)
            ret=ret*a;
    return ret;
}

results matching ""

    No results matching ""