[ABC212E] Safety Journey 题解

思路解析

首先根据题目的条件我们可以想到 dp，用 \(f_{i,j}\) 表示走了 \(i\) 步，现在在 \(j\) 的方案数，可见转移即是 \(f_{i,u} \gets \sum{f_{i-1,v}}\)，这里的 \(v\) 表示每个与 \(u\) 相连的点。可见如此做时间复杂度为 \(O(kn(\frac{n(n-1)}{2}-m))=O(k(\frac{n^3-n^2}{2}-nm)) \approx O(kn^3-knm)\)，考虑优化。

可以发现如果我们像上文一样建边总边数可以达到 \(\frac{n(n-1)}{2}-m \approx n^2-m\)，这个大小是很难被接受的，于是我们想到可以建反边，也就是只建被删除的那 \(m\) 条边，这样总边数就只有 \(m\) 条，可以接受，然后对于统计答案就只需要将转移式改成 \(f_{i,u} \gets \sum^{n}_{j=1}{f_{i-1,j}}-\sum{f_{i-1,v}}\) 即可，其中 \(\sum^{n}_{j=1}{f_{i-1,j}}\) 对于每个 \(u\) 都不会变，可以提前处理好。

注意计算 \(f_{i,u}\) 时要先减去 \(f_{i-1,u}\)，同时勤取模。

时间复杂度：虽有三层循环，但第二层内遍历的是每一条边，而总共只有 \(m\) 条边，因此为 \(O(km)\)，可以通过。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5010, q = 998244353;
int n, m, k, f[N][N];
vector<int> g[N];
void mod(int &x) {
	x = (x % q + q) % q;
}
signed main() {
	cin >> n >> m >> k;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back(v); g[v].push_back(u);
	}
	f[0][1] = 1;
	for(int i = 1; i <= k; i++) {
		int sum = 0;
		for(int j = 1; j <= n; j++) sum += f[i - 1][j], mod(sum);
		for(int j = 1; j <= n; j++) {
			f[i][j] = sum - f[i - 1][j]; mod(f[i][j]);
			for(auto it : g[j]) {
				f[i][j] -= f[i - 1][it]; mod(f[i][j]);
			}
		}
	}
	cout << f[k][1];
	return 0;
}