自动搬运

查看原文

来自洛谷，原作者为

	子丑 ZeeTue

搬运于2025-08-24 22:39:39，当前版本为作者最后更新于2022-08-05 22:37:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

前置知识：

差分，容斥。

题意：

• 给出一张有向图，对房间 $i$ 有若干条边连向区间 $[l_i,r_i]$ 中的所有点。
• $q$ 次询问，每次问从点 $a$ 出发，恰通过 $m$ 条边且不经过点 $c$ 到达点 $b$ 的方案数。

分析：

是一道容斥+dp+小幅度卡空间题。

Subtask0：

dfs 暴力搜索。

Subtask2:

先来看看没有容斥、不卡空间的 dp 该怎么做。

考虑一个 dp 数组 $f_{k,s,t}$，表示从 $s$ 经过 $k$ 条边到达 $t$ 的方案数。转移方程是 $f_{k,s,t}\gets\sum_{(v,t)\in E}$ $f_{k-1,s,v}$，时间复杂度为 $O(n^3m)$。将这个方程反过来，就是 $f_{k-1,s,v}\to f_{k,s,t}\quad((v,t)\in E)$。关注到每个点所到达的点都在一个区间中，也就是说这个式子是一个区间加法。区间加法可以通过前缀和或者差分实现。这里我选择差分，那么转移就变成了如下：

for(int k=1; k<=M; ++k) {
	for(int s=1; s<=n; ++s) {
		for(int t=1; t<=n; ++t) {
			f[k][s][L[t]]+=f[k-1][s][t];
			f[k][s][R[t]+1]-=f[k-1][s][t];
		}
		for(int t=1; t<=n; ++t) {
			f[k][s][t]+=f[k][s][t-1];
		}
	}
}

询问可以在线回答：

while(q--) {
	int a=read(), b=read(), c=read(), m=read();//这里的c暂时没用
	printf("%d\n", f[m][a][b]);
}

Subtask3:

加入容斥，显然不经过点 $c$ 的方案等价于所有方案减去经过点 $c$ 的方案。一种很符合直觉的计算经过点 $c$ 方案数的方法是 $\sum_{i=0}^kf_{i,s,c}\cdot f_{k-i,c,t}$，但是很显然，这样会有重复的方案。当两个方案中最后一次经过 $c$ 点的时间不同时，这两个方案一定不同，并且我们知道单个 $f$ 数组中并没有重复的方案，那么就可以通过枚举最后一次经过 $c$ 点的时间来进行计算。现在再增加一个 dp 数组 $g_{k,s,t}$，表示从 $s$ 出发，经过 $k$ 条边且不再经过 $s$ 到达 $t$ 的方案数，这样就可以通过 $\sum_{i=0}^kf_{i,s,c}\cdot g_{k-i,c,t}$ 来计算不重复的经过点 $c$ 的方案数了。在转移数组 $g$ 时，只需要令 $g_{k,s,s}$ 的值始终为 $0$，就可以保证所有 $g_{k,s,t}$ 方案都没有再次经过点 $s$。转移如下：

for(int k=1; k<=M; ++k) {
	for(int s=1; s<=n; ++s) {
		for(int t=1; t<=n; ++t) {
			f[k][s][L[t]]+=f[k-1][s][t], f[k][s][R[t]+1]-=f[k-1][s][t];
			g[k][s][L[t]]+=g[k-1][s][t], g[k][s][R[t]+1]-=g[k-1][s][t];
		}
 		for(int t=1; t<=n; ++t) {
			f[k][s][t]+=f[k][s][t-1];
			g[k][s][t]+=g[k][s][t-1];
		}
		g[k][s][s]=0;
	}
}

询问仍然是在线回答：

while(q--) {
	int a=read(), b=read(), c=read(), m=read(), ans=f[m][a][b];
	for(int i=0; i<=m; ++i) ans-=f[i][a][c]*g[m-i][c][b];
	printf("%d\n", ans);
}

Subtask4:

不出意外的话，此时的数组大小在 200MB 上下，完全无法通过 128MB 的限制。但是询问是可以离线的，意味着我们并不需要将 $f$ 和 $g$ 两个数组都完全存下来。这里选择滚动 $g$ 数组，所以先把 $f$ 数组计算出来，然后在滚动计算数组 $g$ 的同时计算答案。主题代码如下（未进行取模）：

#define rep(i, a, b) ...
inline int read(){...};
const int N=502, M=100, Q=1e5+1;

int n, q, L[N], R[N], f[M+2][N][N], g[2][N][N];
struct Que {
	int a, b, c, m, ans;
	inline void sol(int k) {
		if(k<=m) ans-=f[m-k][a][c]*g[k&1][c][b];
	}
} que[Q];
inline Que get() {
	int a=read(), b=read(), c=read(), m=read();
	return Que(a, b, c, m, f[m][a][b]);
}

int main() {
	//输入 
	n=read(), q=read();
	rep(i, 1, n) {
		L[i]=read(), R[i]=read();
		f[0][i][i]=g[0][i][i]=1;
		if(!L[i]) L[i]=1;
	}
	//计算数组 f 
	rep(k, 1, M) {
		rep(s, 1, n) {
			rep(t, 1, n) {
				f[k][s][L[t]]+=f[k-1][s][t]);
				f[k][s][R[t]+1]-=f[k-1][s][t];
			}
			rep(t, 1, n) {
				f[k][s][t]+=f[k][s][t-1];
			}
		}
	}
	//输入与预处理询问 
	rep(i, 1, q) {
		que[i]=get();
		que[i].sol(0);
	}
	//计算数组 g 与答案 
	rep(k, 1, M) {
		bool kk=k&1, tk=kk^1;
		memset(g[kk], 0, sizeof(g[kk]));
		rep(s, 1, n) {
			rep(t, 1, n) {
				g[kk][s][L[t]]+=g[tk][s][t];
				g[kk][s][R[t]+1]-=g[tk][s][t];
			}
			rep(t, 1, n) {
				g[kk][s][t]+=g[kk][s][t-1];
			}
			g[kk][s][s]=0;
		}
		rep(i, 1, q) que[i].sol(k);
	}
	//输出答案 
	rep(i, 1, q) printf("%d\n", que[i].ans);
}

时间复杂度为 $O(n^2m+mq)$，空间大概在 100MB 上下。

其他的话

本题可以进一步对空间进行常数级别的优化，最后将空间控制在 54MB 上下，是通过只存储奇数步的 $f$ 数组来完成的，在计算答案的时候对 $f$ 进行一次转移。但是这种方案是用时间换空间，本质上并无区别，（并且肯定会被骂）所以就没有作为本题正解。