题目传送门：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;
}
文章评论