Atcoder ABC244E - King Bombee 题解

原题：

Atcoder ABC244E - King Bombee

题意

给你一张图，从 \(S\) 到 \(T\)，经过 \(k\) 条边， 经过 \(X\) 号点偶数次的方案数。

做法

设 \(f_{i, j, k}\) 表示经过 \(i\) 条边，现在在 \(j\)，经过 \(X\) 的次数的奇偶。

初始状态：

\(f_{0, S, 0} = 1\)

状态转移：

\(f_{i, u, k} = \sum_{(u, v) \in E}f_{i - 1, v, k}(u \ne X)\)

\(f_{i, u, k} = \sum_{(u, v) \in E}f_{i - 1, v, 1 - k}(u = X)\)

即如果当前节点为 \(X\)，那么从上一个节点到这个节点需要改变奇偶（因为到达 \(X\) 的点数会 \(+ 1\) 所以会改变奇偶性。

对应：

\(f_{i, u, k} = \sum_{(u, v) \in E}f_{i - 1, v, 1 - k}(u = X)\)

如果当前节点不为 \(X\)，那么奇偶性不会变。

对应：

\(f_{i, u, k} = \sum_{(u, v) \in E}f_{i - 1, v, k}(u \ne X)\)

C++ 代码

记录：戳这里

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, M = 4010, mod = 998244353;

struct Edge {
    int to;
    int next;
}e[M];

int head[N], idx;

void add(int a, int b) {
    idx++;
    e[idx].to = b;
    e[idx].next = head[a];
    head[a] = idx;
}

int f[N][N][2];

int n, m, k, s, t, x;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k >> s >> t >> x;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }

    f[0][s][0] = 1;
    
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            for (int l = head[j]; l; l = e[l].next) {
                int to = e[l].to;
                for (int r = 0; r <= 1; r++) {
                    if (j == x) f[i][j][r] = (f[i][j][r] + f[i - 1][to][1 - r]) % mod;
                    else f[i][j][r] = (f[i][j][r] + f[i - 1][to][r]) % mod;
                }
            }
        }
    }
    cout << f[k][t][0] << '\n';
    return 0;
}