题目传送门:E - King Bombee (atcoder.jp)
没错,就是一个纯纯的DP,难在状态表示。
一开始我也以为是图论,但是观察到特点:取模、数据范围、奇偶性、求方案数。这些可都是DP的显著特征啊,于是考虑使用dp。
题目描述请看原题,自己翻译一下。
思路
这题难就难在表示状态,我们用dp[i][j][k]表示第i个点,在时间j(时间就是在序列中的位置),走过x的次数为奇数或偶数(1奇数,0偶数)。
我们将边存下来,离线处理,每次dp都是遍历所有边。
表示完成之后就可以写状态转移方程了,不难发现,转移过程应该分两类,设边为[U, V],我们举例单向边的,双向边也一样。

我们观察到这两个方程的差别其实不大,而且是0 和 1相反的操作,就可以将U == X引入到下标中去,减少代码量,也提高逻辑性。

既然万事俱备了,直接敲代码吧~
记得取模!
代码
/*Copyright (C) Eriktse 2022*/ #include <bits/stdc++.h> #define pr printf #define pb push_back #define fi first #define se second #define int long long using namespace std; int readInt() { int s = 0, w = 1;char ch = getchar(); while(ch > '9' || ch < '0'){if(ch == '-')w = -1;ch = getchar();} while('0' <= ch && ch <= '9')s = s * 10 + ch - '0',ch = getchar(); return s * w; } typedef pair<int, int> PII; const int maxn = 2010, p = 998244353; int N, M, K, S, T, X;//N点,M边,构造K长度的路径,ST起点终点,X点出现偶数次 PII v[maxn]; int dp[maxn][maxn][2];//dp[点][时间][次数] signed main() { cin >> N >> M >> K >> S >> T >> X; for(int i = 1;i <= M; ++ i)v[i] = {readInt(), readInt()}; dp[S][0][0] = 1; for(int i = 0;i < K; ++ i)//时间为i for(int j = 1;j <= M; ++ j) { int x = v[j].fi, y = v[j].se; for(int k = 0;k <= 1; ++ k) { (dp[y][i + 1][k] += dp[x][i][k ^ (x == X)]) %= p; (dp[x][i + 1][k] += dp[y][i][k ^ (y == X)]) %= p; } } cout << dp[T][K][0] << '\n'; return 0; }
Comments NOTHING