题解

#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
static const int maxn = 1000000;
static char b[maxn];
static int pos = 0,len = 0;
if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
if(pos == len) return -1;
return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
LL f = 1,x = 0;int s = getchar();
while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
if(!x) {putchar('0');return ;}
if(x<0) putchar('-'),x = -x;
return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

const int MOD = 1000000007;
int n,m,s,o,k;
void MD(int &x) {if(x>=MOD)x-=MOD;}
struct mat{
int s[60][60],n,m;
mat(){memset(s,0,sizeof(s));n=m=0;}
}G,dp0[65],pw0[65],dpl[65],dpr[65];
inline mat operator * (mat a,mat b) {
mat c; c.n = a.n; c.m = b.m;
for(int i = 0;i < a.n;i ++) {
for(int k = 0;k < a.m;k ++) {
if(a.s[i][k])
for(int j = 0;j < b.m;j ++) {
c.s[i][j] = (c.s[i][j] + a.s[i][k]1llb.s[k][j]) % MOD;
}
}
} return c;
}
inline mat operator + (mat a,mat b) {
for(int i = 0;i < a.n;i ++) {
for(int j = 0;j < a.m;j ++) {
MD(a.s[i][j] += b.s[i][j]);
}
} return a;
}
inline mat& operator += (mat &a,mat b) {
for(int i = 0;i < a.n;i ++) {
for(int j = 0;j < a.m;j ++) {
MD(a.s[i][j] += b.s[i][j]);
}
} return a;
}
int main() {
n = read(); k = read(); m = read();
G.n = G.m = n;
for(int i = 0;i <= k;i ++) dp0[i].n = dp0[i].m = n;
for(int i = 1;i <= n;i ++) {
for(int j = 1;j <= n;j ++) {
char c = getchar();
while(c == ' ' || c == '\n') c = getchar();
G.s[i-1][j-1] = c^48;
}
}
mat mt0 = mat();
mt0.n = mt0.m = n;
mat mt1 = mt0,ml0 = mat(),mr0 = mat();
ml0.n = 1; ml0.m = n;
mr0.n = n; mr0.m = 1;
for(int i = 0;i < n;i ++) mt1.s[i][i] = 1;
dp0[1] = G; pw0[1] = dp0[1] * dp0[1];
for(int i = 2;i <= k;i ++) {
dp0[i] = pw0[i-1] + G;
pw0[i] = dp0[i] * dp0[i];
pw0[i] += pw0[i-1];
}
while(m --) {
s = read(); int S = read();
o = read(); int T = read();
if(s > o) swap(s,o);
for(int i = 1;i <= k;i ++) dpl[i] = ml0,dpr[i] = mr0;
dpl[s].s[0][S-1] = 1; dpr[o].s[T-1][0] = 1;
for(int i = s;i <= k;i ++) {
mat nm = dpl[i] * dp0[i];
for(int j = i+1;j <= k;j ++) dpl[j] += nm;
}
for(int i = o;i <= k;i ++) {
mat nm = dp0[i] * dpr[i];
for(int j = i+1;j <= k;j ++) dpr[j] += nm;
}
mat as = dpl[o] * dpr[o];
for(int i = o+1;i <= k;i ++) as += dpl[i] * dpr[i];
AIput(as.s[0][0],'\n');
}
return 0;
}