ABC244E - King Bombee

考え方

まずは，$X$を偶数回云々を抜きにした，一段簡単な問題を考える．

再帰で全ての道順を試して，$K$個の辺を通ったらreturnする方針では間に合わない（$\pmod{998244353}$を要求されていることからもわかるように）．

そこで「ある頂点に行く方法の数」をカウントしておき，その情報をもとに「次の頂点に行く方法の数」を計算する漸化式が必要になる．この考え方だと，あるステップで頂点$v$にたどり着く方法（※）を1つに束ねて次のステップを計算できるので，全ての道順を試す再帰より計算量がはるかに小さくて済む（再帰の場合は※を全て区別する）．

漸化式のステップとして使えるのは，通った辺の個数しかない．そこで，
dp[i][v] = (頂点$S$から$i$個の辺を通って頂点$v$に行く方法の数)
とする．このとき，各ステップ$i$で「全ての頂点と頂点から出ている辺」を見れば次のステップ$i+1$を計算できる．辺の一端の情報をもとにもう一端を更新するので，計算量は$O(K\cdot 2M)$．

---

次に，$X$をを通った回数の偶奇性を記録する方法を考える．もし，単に上のdpを偶数・奇数で別々につくって上手く遷移できれば簡単である．

遷移方法を考えると，$v = X$のときに一方から他方へ移ればよいだけであるから，これでうまくいくことがわかる．

回答例

mod = 998244353
N, M, K, S, T, X = map(int, input().split())
S -= 1
T -= 1
X -= 1
G = [[] for _ in range(N)]
for _ in range(M):
    U, V = map(int, input().split())
    U -= 1
    V -= 1
    G[U].append(V)
    G[V].append(U)

dp_even = [[0] * N for _ in range(K + 1)]
dp_odd = [[0] * N for _ in range(K + 1)]
dp_even[0][S] = 1

for i in range(K):
    for v in range(N):
        for chi in G[v]:
            if chi != X:
                dp_even[i + 1][chi] += dp_even[i][v]
                dp_odd[i + 1][chi] += dp_odd[i][v]
            else:
                dp_even[i + 1][chi] += dp_odd[i][v]
                dp_odd[i + 1][chi] += dp_even[i][v]
            dp_even[i + 1][chi] %= mod
            dp_odd[i + 1][chi] %= mod

print(dp_even[K][T])