Yet another 1e9+7
Yet another 计数 dp
Yet another 我做不出来的题
考虑合法的按键方式长啥样。假设我们依次按下了 (p_1,p_2,dots,p_m) 号按键。
若 (m=1)，则序列 (p_1,p_2,dots,p_m) 显然合法。
若 (m>1)，则 (p_1,p_2,dots,p_m) 必须有唯一最大值 (x)（否则的话第二次按 (x) 的时候就不合法了）。假设 (x) 将原序列分成两个子序列 (p_1,p_2,dots,p_{k-1}) 和 (p_{k+1},p_{k+2},dots,p_{m})，那么这两个序列的最大值必须都小于 (x)，否则原序列就不会有唯一最大值 (x) 了。并且 (p_1,p_2,dots,p_{k-1}) 和 (p_{k+1},p_{k+2},dots,p_{m}) 也必须是合法序列。
形式化地说，(p_1,p_2,dots,p_m) 必须是一个大根堆的中序遍历。
这样就可以 (dp) 了。设 (dp_{a,b,c,x1,x2}) 表示起点为 (a)，终点为 (b)，按下的按键的编号都 (leq c) 的合法的行走路线个数。(x1) 表示是否对第一次的按键有要求，(x2) 表示是否对最后一次的按键有要求。
先考虑 (x1=x2=0) 的情况，即对起点和终点按键都没有要求。
那么有以下两种转移方式：
- 按键序列中按下的编号最大的按键 (<c)，则 (dp_{a,b,c,0,0}=dp_{a,b,c-1,0,0})
- 若按键序列中按下的编号最大的按键 (=c)，那么我们枚举在 (k) 点按下编号为 (c) 的键，那么 (a) 到 (b) 的路径被我们拆成了两部分 (a o k) 和 (k o b)。我们进一步枚举 (k) 之前到达的点 (u) 和 (k) 接下来到达的点 (v)，那么根据之前的推论，(a o u) 路径上我们只能按下编号 (leq c-1) 的键，(v o b) 的路径上我们也只能按下编号 (leq c-1) 的键。故我们有 (dp_{a,b,c,0,0}=sumlimits_{k}sumlimits_{(u,k)}sumlimits_{(k,v)}dp_{a,u,c-1,0,0} imes dp_{v,b,c-1,0,0})，记 (f_{a,k,c}=sumlimits_{(u,k)}dp_{a,u,c-1,0,0})， (g_{b,k,c}=sumlimits_{(k,v)}dp_{v,b,c-1,0,0})，那么上述式子可优化为 (dp_{a,b,c,0,0}=sumlimits_{k}f_{a,k,c} imes g_{b,k,c})（当然，如果 (k=a) 那么 (k) 可以是路径当中第一个点，此时就不存在 (k) 之前的点了，故令所有 (f_{a,a,c}) 加 (1) 即可，(g_{b,b,c}) 同理）。
紧接着是 (x1
eq 0) 或 (x2
eq 0) 的情况，这里以 (x1=1,x2=0) 的情况为例，其它两种情况同理。
还是分两种情况（其实与之前那种情况大差不差）：
- 按键序列中按下的编号最大的按键 (<c)，则 (dp_{a,b,c,1,0}=dp_{a,b,c-1,1,0})。
- 若按键序列中按下的编号最大的按键 (=c)， (dp_{a,b,c,1,0}=sumlimits_{k}sumlimits_{(u,k)}sumlimits_{(k,v)}dp_{a,u,c-1,1,0} imes dp_{v,b,c-1,0,0})，你还是记 (f_{a,k,c}=sumlimits_{(u,k)}dp_{a,u,c-1,1,0})， (g_{b,k,c}=sumlimits_{(k,v)}dp_{v,b,c-1,0,0})，将上述式子优化为 (dp_{a,b,c,1,0}=sumlimits_{k}f_{a,k,c} imes g_{b,k,c})（只不过 (k=a) 的情况要改一下，只有当 (c=bs) 的时候才能令 (f_{a,a,c}) 加 (1)）
这样 (dp) 一遍是 (n^4) 的，加上 (q) 次询问的条件，显然不能让我们满意。
不过发现对于每组询问，只有当 (a=s) 的时候 (dp_{a,b,c,1,0}) 才有意义，只有当 (b=t) 的时候 (dp_{a,b,c,0,1}) 才有意义。所以可以预处理出 (dp_{a,b,c,0,0}) 的值，对于每组询问重新计算 (dp_{a,b,c,0,1},dp_{a,b,c,1,0},dp_{a,b,c,1,1}) 的值。这样总复杂度就降到了 (n^4+qn^3)。
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=1;
while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=neg;
}
const int MAXN=60;
const int MOD=1e9+7;
int n,k,qu;
char ed[MAXN+5][MAXN+5];
int dp[2][2][MAXN+5][MAXN+5][MAXN+5],f[2][MAXN+5][MAXN+5][MAXN+5],g[2][MAXN+5][MAXN+5][MAXN+5];
void prework(){
for(int x=1;x<=k;x++){
for(int i=1;i<=n;i++) for(int k=1;k<=n;k++) for(int l=1;l<=n;l++)
if(ed[l][k]=='1') f[0][i][k][x]=(f[0][i][k][x]+dp[0][0][i][l][x-1])%MOD;
for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) for(int l=1;l<=n;l++)
if(ed[k][l]=='1') g[0][j][k][x]=(g[0][j][k][x]+dp[0][0][l][j][x-1])%MOD;
for(int i=1;i<=n;i++) f[0][i][i][x]=(f[0][i][i][x]+1)%MOD;
for(int i=1;i<=n;i++) g[0][i][i][x]=(g[0][i][i][x]+1)%MOD;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[0][0][i][j][x]=dp[0][0][i][j][x-1];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
dp[0][0][i][j][x]=(dp[0][0][i][j][x]+1ll*f[0][i][k][x]*g[0][j][k][x]%MOD)%MOD;
}
}
int query(int s,int bs,int t,int bt){
fill0(dp[1][0]);fill0(dp[0][1]);fill0(dp[1][1]);fill0(f[1]);fill0(g[1]);
for(int x=1;x<=k;x++){
for(int k=1;k<=n;k++) for(int l=1;l<=n;l++)
if(ed[l][k]=='1') f[1][s][k][x]=(f[1][s][k][x]+dp[1][0][s][l][x-1])%MOD;
for(int k=1;k<=n;k++) for(int l=1;l<=n;l++)
if(ed[k][l]=='1') g[1][t][k][x]=(g[1][t][k][x]+dp[0][1][l][t][x-1])%MOD;
if(x==bs) f[1][s][s][x]=(f[1][s][s][x]+1)%MOD;
if(x==bt) g[1][t][t][x]=(g[1][t][t][x]+1)%MOD;
for(int i=1;i<=n;i++){
dp[1][0][s][i][x]=dp[1][0][s][i][x-1];
dp[0][1][i][t][x]=dp[0][1][i][t][x-1];
for(int k=1;k<=n;k++){
dp[1][0][s][i][x]=(dp[1][0][s][i][x]+1ll*f[1][s][k][x]*g[0][i][k][x]%MOD)%MOD;
dp[0][1][i][t][x]=(dp[0][1][i][t][x]+1ll*f[0][i][k][x]*g[1][t][k][x]%MOD)%MOD;
}
}
dp[1][1][s][t][x]=dp[1][1][s][t][x-1];
for(int k=1;k<=n;k++){
dp[1][1][s][t][x]=(dp[1][1][s][t][x]+1ll*f[1][s][k][x]*g[1][t][k][x]%MOD)%MOD;
}
}
return dp[1][1][s][t][k];
}
int main(){
scanf("%d%d%d",&n,&k,&qu);
for(int i=1;i<=n;i++) scanf("%s",ed[i]+1);
prework();
while(qu--){
int s,bs,t,bt;scanf("%d%d%d%d",&bs,&s,&bt,&t);
printf("%d
",query(s,bs,t,bt));
}
return 0;
}
/*
6 3 8
010000
001000
000100
000010
000000
000001
1 1 1 1
3 3 1 1
1 1 3 3
1 1 1 5
2 1 1 5
1 1 2 5
3 1 3 5
2 6 2 6
*/