ABC212E - Safety Journey

問題

https://atcoder.jp/contests/abc212/tasks/abc212_e

略説

dp[i][j] := i日目に都市jにいる場合の数

dp[i+1][j] = sum(dp[i]) - dp[i][k:=都市kと都市jは結ばれていない]

iについての各ループにおいて、kの総数は高々2M+Nとなる。

よって計算量は O(K(N+M)) となる。

ACコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <unsigned int MOD>
struct Modint {
    unsigned int x;
    constexpr Modint(): x(0) {}
    template <typename T>
    constexpr Modint(T _x) noexcept : x((_x%=MOD)<0 ? _x+MOD : _x) {}
    constexpr Modint inv() const noexcept {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Modint(u);
    }
    constexpr Modint operator+() const noexcept {return *this;}
    constexpr Modint operator-() const noexcept {return Modint()-*this;}
    constexpr Modint &operator++() noexcept {
        if (++x == MOD) x = 0;
        return *this;
    }
    constexpr Modint &operator--() noexcept {
        if (x-- == 0) x += MOD;
        return *this;
    }
    constexpr Modint operator++(int) noexcept {
        Modint res = *this;
        ++*this;
        return res;
    }
    constexpr Modint operator--(int) noexcept {
        Modint res = *this;
        --*this;
        return res;
    }
    constexpr Modint &operator+=(const Modint &y) noexcept {
        if ((x+=y.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr Modint &operator-=(const Modint &y) noexcept {
        if (x < y.x) x += MOD;
        x -= y.x;
        return *this;
    }
    constexpr Modint &operator*=(const Modint &y) noexcept {
        x = (unsigned long long)x*y.x%MOD;
        return *this;
    }
    constexpr Modint &operator/=(const Modint &y) noexcept {return *this*=y.inv();}
    friend constexpr Modint operator+(const Modint &l, const Modint &r) {return Modint(l)+=r;}
    friend constexpr Modint operator-(const Modint &l, const Modint &r) {return Modint(l)-=r;}
    friend constexpr Modint operator*(const Modint &l, const Modint &r) {return Modint(l)*=r;}
    friend constexpr Modint operator/(const Modint &l, const Modint &r) {return Modint(l)/=r;}
    friend constexpr bool operator==(const Modint &l, const Modint &r) {return l.x==r.x;}
    friend constexpr bool operator!=(const Modint &l, const Modint &r) {return l.x!=r.x;}
    friend constexpr istream &operator>>(istream &is, Modint &y) {
        long long z;
        y = (is>>z, z);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const Modint &y) {return os<<y.x;}
};

using mint = Modint<998244353>;

int N, M, K;
vector<int> G[5050];
mint dp[5050][5050];

void solve() {
    cin >> N >> M >> K;
    for (int i=0; i<M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dp[0][0] = 1;
    mint sum = 1;
    for (int i=0; i<K; i++) {
        fill(dp[i+1], dp[i+1]+N, sum);
        sum = 0;
        for (int j=0; j<N; j++) {
            for (int k: G[j]) dp[i+1][j] -= dp[i][k];
            dp[i+1][j] -= dp[i][j];
            sum += dp[i+1][j];
        }
    }
    cout << dp[K][0] << '\n';
}

signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}