题解 P7155 【[USACO20DEC] Spaceship P】

tzc_wk · 2020-12-26 16:50:22 · 题解

Portal

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\to k 和 k\to b。我们进一步枚举 k 之前到达的点 u 和 k 接下来到达的点 v，那么根据之前的推论，a\to u 路径上我们只能按下编号 \leq c-1 的键，v\to b 的路径上我们也只能按下编号 \leq c-1 的键。故我们有 dp_{a,b,c,0,0}=\sum\limits_{k}\sum\limits_{(u,k)}\sum\limits_{(k,v)}dp_{a,u,c-1,0,0}\times dp_{v,b,c-1,0,0}，记 f_{a,k,c}=\sum\limits_{(u,k)}dp_{a,u,c-1,0,0}， g_{b,k,c}=\sum\limits_{(k,v)}dp_{v,b,c-1,0,0}，那么上述式子可优化为 dp_{a,b,c,0,0}=\sum\limits_{k}f_{a,k,c}\times g_{b,k,c}（当然，如果 k=a 那么 k 可以是路径当中第一个点，此时就不存在 k 之前的点了，故令所有 f_{a,a,c} 加 1 即可，g_{b,b,c} 同理）。

紧接着是 x1\neq 0 或 x2\neq 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}=\sum\limits_{k}\sum\limits_{(u,k)}\sum\limits_{(k,v)}dp_{a,u,c-1,1,0}\times dp_{v,b,c-1,0,0}，你还是记 f_{a,k,c}=\sum\limits_{(u,k)}dp_{a,u,c-1,1,0}， g_{b,k,c}=\sum\limits_{(k,v)}dp_{v,b,c-1,0,0}，将上述式子优化为 dp_{a,b,c,1,0}=\sum\limits_{k}f_{a,k,c}\times 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\n",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
*/