洛谷 P7155 [USACO20DEC] Spaceship P（dp）

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

*/

巴特西

洛谷 P7155 [USACO20DEC] Spaceship P（dp）

最新文章

热门文章