学步园

无聊写了个矩阵的模板，传上备用。

Matrix preSum(Matrix A,int k)
{
    if(k == 1)
        return A;
    Matrix sum = preSum(A,k/2);
    if(k&1)
    {
        Matrix Ak_1 = A.pow(k/2+1);
        return sum + Ak_1 + Ak_1*sum;
    }
    else
    {
        Matrix Ak = A.pow(k/2);
        return Sum + Ak*sum;
    }
}

#include <stdio.h>
#include <string.h>

typedef long long LL;

const int N = 3;

int mod = 1e9+7;

struct Matrix
{
    int r,c;
    int m[N][N];
    Matrix(){}
    Matrix(int r,int c):r(r),c(c){}
    Matrix operator *(const Matrix& B)
    {
        Matrix T(r,B.c);
        for(int i=1;i<=T.r;i++)
        {
            for(int j=1;j<=T.c;j++)
            {
                LL tt = 0;
                for(int k=1;k<=c;k++)
                    tt += (LL)m[i][k] * B.m[k][j] % mod;
                T.m[i][j] = tt % mod;
            }
        }
        return T;
    }
    Matrix operator +(const Matrix& B)
    {
        Matrix T(r,c);
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                T.m[i][j] = (m[i][j]+B.m[i][j]) % mod;
        return T;
    }
    Matrix unit()
    {
        Matrix T(r,r);
        memset(T.m,0,sizeof(T.m));
        for(int i=1;i<=r;i++)
            T.m[i][i] = 1;
        return T;
    }
    Matrix pow(int n)
    {
        Matrix res = unit() , base(*this);
        while(n)
        {
            if(n&1)
                res = res*base;
            base = base*base;
            n >>= 1;
        }
        return res;
    }
    void init()
    {
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                scanf("%d",&m[i][j]);
    }
    void print()
    {
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
                printf("%d ",m[i][j]);
            puts("");
        }
    }
};