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