FCS NOI2018 一试 GG记

#include<cstdio>
#include<cstdlib>
using namespace std;
const int mod=1e9+7;
int O[1001][21],I[1001][21];
int n,m,q,x,y,z,ans;
int f[1001];
struct matrix{
    int a[21][21];
    matrix(){
        for(register int i=0;i<m;++i)
            for(register int j=0;j<m;++j)
                a[i][j]=0;
    }
    inline matrix operator*(matrix A)const{
        matrix ret;
        for(register int i=0;i<m;++i)
            for(register int j=0;j<m;++j)
                for(register int k=0;k<m;++k)
                    ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*A.a[k][j]%mod)%mod;
        return ret;
    }
    inline matrix operator+(matrix A)const{
        matrix ret;
        for(register int i=0;i<m;++i)
            for(register int j=0;j<m;++j){
                ret.a[i][j]=a[i][j]+A.a[i][j];
                if(ret.a[i][j]>=mod)
                    ret.a[i][j]-=mod;
            }
        return ret; 
    } 
}A[51],B[51],G,S;
inline void calc(int n){
    for(register int i=0;i<m;++i)
        for(register int j=0;j<m;++j)
            G.a[i][j]=S.a[i][j]=0;
    for(register int i=0;i<m;++i)
        G.a[i][i]=S.a[i][i]=1;
    for(register int i=0;i<=31;++i)
        if((n>>i)&1){
            S=S+(B[i]*G);
            G=G*A[i];
        }
}
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=0;i<n;++i){
        for(register int j=0;j<m;++j)scanf("%d",O[i]+j),O[i][j]%=mod;
        for(register int j=0;j<m;++j)scanf("%d",I[i]+j),I[i][j]%=mod;
    }
    for(register int k=0;k<n;++k)
        for(register int i=0;i<m;++i)
            for(register int j=0;j<m;++j)
                A[0].a[i][j]=(A[0].a[i][j]+1ll*I[k][i]*O[k][j]%mod)%mod;
    B[0]=A[0];
    for(register int i=0;i<=31;++i){
        A[i+1]=A[i]*A[i];
        for(register int j=0;j<m;++j)
            ++A[i].a[j][j];
        B[i+1]=B[i]*A[i];
        for(register int j=0;j<m;++j)
            --A[i].a[j][j]; 
    }
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&x,&y,&z);--x;--y;
        if(!z){
            printf("%d\n",(x==y));
            continue;
        }
        calc(z-1);
        for(register int i=0;i<m;++i)f[i]=0; 
        ans=0;
        for(register int i=0;i<m;++i)
            for(register int j=0;j<m;++j)
                f[i]=(f[i]+1ll*O[x][j]*S.a[j][i]%mod)%mod;
        for(register int i=0;i<m;++i)
            ans=(ans+1ll*I[y][i]*f[i]%mod)%mod;
        printf("%d\n",(ans+(x==y))%mod);
    }
    return 0;
}