「USACO 2020.12 Platinum」Spaceship

看到题目第一个想到的是：按照路径长度可以确定按钮次数和路径次数

然而路径长度是$2^k$级别的。。

下文认为$n,q,k$同阶

既然无法考虑长度，那么就直接在$dp$时将路径作为状态压入

令$dp_{i,s,t}$表示前面$i$个按钮未按过，从$s$走到$t$的路径数

显然$dp_{i}$可以看做一个类似矩阵的转移，设邻接矩阵为$E$

那么得到$dp_{i}=dp_{i-1}+dp_{i-1}\cdot E\cdot dp_{i-1}$

($dp_i$不一定按了$i$这个按钮，所以考虑按或者不按)

那么对于$b_s,b_t$的情况，考虑把操作序列分成两段

显然操作序列有唯一一个按过恰好一次的最大的按钮$max$，可以在这里将操作序列分成两段

处理出$b_s$到$max$和$max$到$b_t$的两部分方案数合并即可

以处理$b_s\rightarrow max$为例

类似上面的操作，令$F_{i,j}$表示最大按钮为$i$，且按过$i$之后没有按过其他按钮，停留在$j$的方案数 ($F_i$是一个向量)

初始显然有$F_{b_s,s}=1$

$\displaystyle i>b_s,F_{i}=\sum_{j<i} F_{j}\cdot dp_{j-1}\cdot E$(按过$j$之后可以继续按$[1,j-1]$)

前缀和即可，复杂度为$O(n^3)$

同理处理出$max\rightarrow b_t$的权值合并即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
#define Mod1(x) ((x>=P)&&(x-=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=62,P=1e9+7,INF=1e9+10;

int n,m,q;
struct Mat{
	int a[N][N];
	void clear(){ memset(a,0,sizeof a); }
	Mat operator * (const Mat &x) const {
		Mat res; res.clear();
		rep(i,1,n) rep(j,1,n) if(a[i][j]) rep(k,1,n) res.a[i][k]=(res.a[i][k]+1ll*a[i][j]*x.a[j][k])%P;
		return res;
	}
	Mat operator + (const Mat &x) const {
		Mat res;
		rep(i,1,n) rep(j,1,n) res.a[i][j]=a[i][j]+x.a[i][j],Mod1(res.a[i][j]);
		return res;
	}
} I,E,dp[N];
int F[N][N],G[N][N];
int S[N][N];

int main(){
	freopen("spaceship.in","r",stdin),freopen("spaceship.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	rep(i,1,n) I.a[i][i]=1;
	rep(i,1,n) rep(j,1,n) scanf("%1d",&E.a[i][j]);
	dp[0]=I;
	rep(i,1,m) dp[i]=dp[i-1]+dp[i-1]*E*dp[i-1];
	while(q--) {
		int bs,s,bt,t; scanf("%d%d%d%d",&bs,&s,&bt,&t);
		memset(F,0,sizeof F),memset(G,0,sizeof G);
		memset(S,0,sizeof S);
		F[bs][s]=1;
		rep(i,1,n) S[bs][i]=dp[bs-1].a[s][i];
		rep(i,bs+1,m) {
			rep(a,1,n) if(S[i-1][a]) rep(b,1,n) F[i][b]=(F[i][b]+1ll*S[i-1][a]*E.a[a][b])%P;
			rep(a,1,n) S[i][a]=S[i-1][a];
			rep(a,1,n) if(F[i][a]) rep(b,1,n) S[i][b]=(S[i][b]+1ll*F[i][a]*dp[i-1].a[a][b])%P;
		}

		memset(S,0,sizeof S);
		G[bt][t]=1;
		rep(i,1,n) S[bt][i]=dp[bt-1].a[i][t];
		rep(i,bt+1,m) {
			rep(a,1,n) rep(b,1,n) G[i][a]=(G[i][a]+1ll*S[i-1][b]*E.a[a][b])%P;
			rep(a,1,n) S[i][a]=S[i-1][a];
			rep(a,1,n) rep(b,1,n) S[i][a]=(S[i][a]+1ll*G[i][b]*dp[i-1].a[a][b])%P;
		}

		int ans=0;
		rep(i,1,m) rep(j,1,n) ans=(ans+1ll*F[i][j]*G[i][j])%P;
		printf("%d\n",ans);
	}
}