[ABC244] E - King Bombee
[Q] https://atcoder.jp/contests/abc244/tasks/abc244_e
渡されるパラメータが多いので読み解くのが大変。
グラフはって、DP[index][今いる位置][Xが偶数個か奇数個か] で管理します。
1. DPの初期条件は？
2. DPの遷移は？
3. DPの答えは？
Q. 入力例1
4 4 4 S=1 T=3 X=2
1 2
2 3
3 4
1 4
1. 初期条件
DP[0][1][0] = 1通り // index, 今いる場所, Xの偶奇
からスタート。
index=0, S=1, X=2の個数は、最初は絶対0個なので、偶数(0)としてマッピングします。
2. 遷移
DP[0][1][0]:1 // index, 今いる場所, Xの個数の偶奇(0:偶数 1:奇数)
DP[1][2][1]:1 // DP[0][1][0]から、2 に遷移
DP[1][4][0]:1 // DP[0][1][0]から、4 に遷移
DP[2][1][0]:1
DP[2][1][1]:1
DP[2][3][0]:1
DP[2][3][1]:1
DP[3][2][0]:2
DP[3][2][1]:2
DP[3][4][0]:2
DP[3][4][1]:2
DP[4][1][0]:4
DP[4][1][1]:4
DP[4][3][0]:4
DP[4][3][1]:4
3. 答えは？
T=3で、X=偶数(0)になっているものを選ぶので
DP[4][3][0] = 4 が解答。
一般化すると
DP[K][T][0]
が解答。実装
mint DP[2020][2020][2]; // index, now, is_odd
vector<ll> G[2020];
int main() {
cincout();
ll N, M, K, S, T, X;
cin >> N >> M >> K >> S >> T >> X;
--S, --T, --X;
rep(i, M) {
ll u, v;
cin >> u >> v;
--u, --v;
G[u].push_back(v);
G[v].push_back(u);
}
DP[0][S][0] = 1;
rep(i, K) {
rep(j, N) {
for (auto g : G[j]) {
if (g == X) { // Xに移動する場合は、偶奇を反転させる
DP[i + 1][g][0] += DP[i][j][1];
DP[i + 1][g][1] += DP[i][j][0];
} else { // X以外に移動するなら、前状態の個数をもらうだけ。
DP[i + 1][g][0] += DP[i][j][0];
DP[i + 1][g][1] += DP[i][j][1];
}
}
}
}
cout << DP[K][T][0] << endl;
}