「SOL」Spaceship(LOJ/USACO) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」Spaceship(LOJ/USACO)

发表于 更新于 分类于 Valine：

USACO 好难啊

# 题面

$n$ 个点之间有若干条有向边连接，保证边 $u\to v$ 不超过一条，但可能同时有 $u\to v,v\to u$，也可以有自环。

你有 $m$ 个按钮编号为 $1\sim m$，最初所有按钮都「可用」。当你按下按钮 $x$ 后，按钮 $x$ 会被「禁用」（你不能按当前被禁用的按钮），同时按钮 $1\sim x-1$ 全部恢复成可用。

给定 $Q$ 组询问，每组询问给出 $s,t,b_s,b_t$，表示：你从 $s$ 点出发，开始时强制按钮 $b_s$ 变为「禁用」；你需要按一个按钮，然后走一步；求有多少种方案，满足当你到达 $t$ 点时，你上一次按的按钮为 $b_t$。

数据规模：$n,m,q\le60$。

# 解析

暂时不管 $b_s,b_t$ 的限制。

根据规则，我们按下按钮 $i$ 后，小于 $i$ 的按钮都会重置，于是比较自然地想到计算子问题「只用小于等于 $i$ 的按钮」。

定义朴素 DP 状态：$f(i,s,t)$ 表示「只按小于等于 $i$ 的按钮，从 $s$ 跑到 t$ 有多少种方案」。记 $g(s,t)$ 表示是否存在边 $s\to t$，存在为 $1$，不存在为 $0$。

考虑 $f$ 的转移 —— 「只按小于等于 $i$ 的按钮」，意味着当我们按下 $i$ 后，$i$ 就永远禁用了，于是可以先分两类再拆三段：

  • 不按按钮 $i$：$f(i,s,t)\gets f(i-1,s,t)$（“$\gets$” 在这里表示 “贡献”）；
  • 按按钮 $i$，可以拆成三段：
    • 先在 $1\sim i-1$ 中瞎乱按：$f(i-1,s,x)$；
    • 按按钮 $i$：$e(x,y)$；
    • 再在 $1\sim i-1$ 中瞎乱按：$f(i-1,y,t)$。

记矩阵 $E$：$E_{ij}=e(i,j)$；$F^i$：$F^i_{st}=f(i,s,t)$。

矩阵编号写成下标太难受了 ::>_<::

于是 DP 的转移方程就可以写成：

可以 $\mathcal{O}(n^4)$ 处理出所有的 DP 值。

再考虑 $b_s,b_t$ 的限制。仍然分析「只按小于等于 $b_{mx}$ 的按钮」这样的子问题，不过这次要求一定要按 $b_{mx}$。

把方案从按下 $b_{mx}$ 这个位置分成两半计算，因为 $b_{mx}$ 既然是按的最大的按钮，肯定只能按一次。

定义 DP 状态 $p(i,x)$ 表示：$b_{mx}=i$ 时，从 $s$ 出发，按钮初始状态为“只有 $b_s$ 禁用”，每走一步按一次按钮（这样方便理解一些），走到 $x$ 时按下 $b_{mx}$ 的方案数。

根据定义，DP 初值为 $p(b_s,s)=1$。一种方案可以看成两部分：

  • 只在小于等于 $j$ 的按钮中乱按，从 $s$ 跑到 $y$，且最后按下按钮 $j$（此时小于等于 $j-1$ 的按钮重置）；
  • 在小于等于 $j-1$ 的按钮中乱按，从 $y$ 跑到 $z$；
  • 按下 $i$，从 $z$ 跑到 $x$，结束。

同样，写成矩阵的形式，一个一行 $n$ 列的矩阵。$P^i$：$P^i_{1j}=p(i,j)$。

注意到 $P$ 是 $1\times n$ 的，上述转移可以 $\mathcal{O}(n^3)$ 计算出所有的 $p(i,x)$。

再推导后一半：按下按钮 $b_{mx}$ 最后按 $b_t$。记 $q(i,x)$ 表示 $b_{mx}=i$ 时，从 $x$ 出发，按钮初始状态为“只有 $b_{mx}$ 为禁用”，按一次按钮走一步，走到 $t$ 且最后一次按 $b_t$ 的方案数。

答案则为

注意到 $q$ 和 $p$ 在某种程度上是高度对称的，我们可以较为简单地得到 $q$ 的转移 —— 基本上就是把整个过程倒过来想。

  • 最后在小于等于 $j-1$ 的按钮中乱按，从 $z$ 跑到了 $t$；
  • 之前在小于等于 $j$ 的按钮中乱按，最后一次按了按钮 $j$，从 $y$ 跑到了 $z$；
  • 最开始按了按钮 $i$，从 $x$ 跑到了 $y$。

同理可以 $\mathcal{O}(n^3)$ 求解。

所以总复杂度为 $\mathcal{O}(n^4+Qn^3)$，写成矩阵可以让代码略微好看一些……

# 源代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
const int N=65,MOD=1e9+7;
#define con(type) const type &
inline int add(con(int)a,con(int)b){return a+b>=MOD?a+b-MOD:a+b;}
inline int sub(con(int)a,con(int)b){return a-b<0?a-b+MOD:a-b;}
inline int mul(con(int)a,con(int)b){return int(1ll*a*b%MOD);}
inline int ina_pow(con(int)a,con(int)b){return b?mul(ina_pow(mul(a,a),b>>1),(b&1)?a:1):1;}
inline void upd(int &a,con(int)b){a=add(a,b);}

int n,m,nq;
char str[N];

struct Matrix{
	int mat[N][N];
	Matrix(){memset(mat,0,sizeof mat);}
	inline int* operator [](con(int)i){return mat[i];}
	Matrix operator *(con(Matrix)b)const{
		Matrix c;
		for(int i=1;i<=n;i++)
			for(int k=1;k<=n;k++)
				for(int j=1;j<=n;j++)
					upd(c.mat[i][j],mul(mat[i][k],b.mat[k][j]));
		return c;
	}
	void operator +=(con(Matrix)b){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				upd(mat[i][j],b.mat[i][j]);
	}
}m_tra,m_def[N];

int vs[N][N],vt[N][N],tmp[N],tmp2[N];

int main(){
	// freopen("input.in","r",stdin);
	rin(n),rin(m),rin(nq);
	for(int u=1;u<=n;u++){
		scanf("%s",str+1);
		for(int v=1;v<=n;v++)
			m_tra[u][v]=str[v]=='1';
	}
	for(int i=1;i<=n;i++)
		m_def[0][i][i]=1;
	for(int i=1;i<=m;i++){
		m_def[i]=m_def[i-1];
		m_def[i]+=m_def[i-1]*m_tra*m_def[i-1];
	}
	for(int mq=1,bs,bt,s,t;mq<=nq;mq++){
		rin(bs),rin(s),rin(bt),rin(t);
		memset(vs,0,sizeof vs);
		memset(vt,0,sizeof vt);
		// “走完这一步，按一次按钮” -> “最初在 s 点直接按一次按钮”
		vs[bs][s]=1;
		for(int i=1;i<=n;i++) tmp[i]=m_def[bs-1][s][i];
		for(int i=bs+1;i<=m;i++){
			for(int p=1;p<=n;p++)
				for(int q=1;q<=n;q++)
					upd(vs[i][q],mul(tmp[p],m_tra[p][q]));
			for(int p=1;p<=n;p++)
				for(int q=1;q<=n;q++)
					upd(tmp2[q],mul(vs[i][p],m_def[i-1][p][q]));
			for(int p=1;p<=n;p++) upd(tmp[p],tmp2[p]),tmp2[p]=0;
		}
		// “按一次按钮，走一步” -> “最后在 t 直接按一次”
		vt[bt][t]=1;
		for(int i=1;i<=n;i++) tmp[i]=m_def[bt-1][i][t];
		for(int i=bt+1;i<=m;i++){
			for(int p=1;p<=n;p++)
				for(int q=1;q<=n;q++)
					upd(vt[i][q],mul(tmp[p],m_tra[q][p]));
			for(int p=1;p<=n;p++)
				for(int q=1;q<=n;q++)
					upd(tmp2[q],mul(vt[i][p],m_def[i-1][q][p]));
			for(int p=1;p<=n;p++) upd(tmp[p],tmp2[p]),tmp2[p]=0;
		}
		int ans=0;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				upd(ans,mul(vs[i][j],vt[i][j]));
		printf("%d\n",ans);
	}
	return 0;
}

THE END

Thanks for reading!

是灵台菩提的初萌
是神游蝶茧的悸动
是万物的方生方死
鱼跃方成龙
是弹指白驹的飞纵
是刹那朝菌的临终
待天地封冻 可曾怨西风

——《万象霜天》By 赤羽

> Link 万象霜天-Bilibili