2024-09-22

AtCoder ABC 372 F - Teleporting Takahashi 2 (2D, 青色, 525 点)

$M$ が小さいことがいかにも怪しかったので、グラフを小さくすることを考えた。

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $N + M$ の有向グラフがある。

辺 $i$ ( $i = 0, 1, \dots, N-1$ ) は、頂点 $i$ から頂点 $i+1$ を結ぶ ( $N$ は 0 とする)
辺 $j + N$ ( $j = 0, 1, \dots, M-1$ ) は、頂点 $U_{j}$ から頂点 $V_{j}$ を結ぶ

このグラフ上の、頂点 0 を始点とする長さ $K$ のウォークの本数を 998244353 で割った余りを求めよ。

制約

$N, K \le 2 \times 10^{5}$
$M \le 50$

考えたこと

$N$ に比べて $M$ はとても小さいので、グラフの大部分は「分岐のない一直線」であることがわかる。このことを利用して、グラフのサイズを小さくする。具体的には、頂点 1 と、辺 $N, N+1, \dots, N+M-1$ の両端点の頂点のみからなるグラフを新たに作る。そして、辺に重みがつくことになる。

この頂点数 $O(M)$ 個の新しいグラフ上で、次のような DP を考える。なお、もとの問題の頂点 0 が、新しいグラフでも頂点 0 であるとする。

dp[k][v]：頂点 0 を始点とし、頂点 $v$ を終点とするウォークであって、長さが $k$ であるものの本数

グラフの頂点数も辺数も $O(M)$ であるから、この DP の計算量は $O(MK)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

// modint
template<int MOD> struct Fp {
    // inner value
    long long val;
    
    // constructor
    constexpr Fp() : val(0) { }
    constexpr Fp(long long v) : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr long long get() const { return val; }
    constexpr int get_mod() const { return MOD; }
    
    // arithmetic operators
    constexpr Fp operator + () const { return Fp(*this); }
    constexpr Fp operator - () const { return Fp(0) - Fp(*this); }
    constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp &r) {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp &r) {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp &r) {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp &r) {
        long long a = r.val, 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);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp pow(long long n) const {
        Fp res(1), mul(*this);
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr Fp inv() const {
        Fp res(1), div(*this);
        return res / div;
    }

    // other operators
    constexpr bool operator == (const Fp &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp &r) const {
        return this->val != r.val;
    }
    constexpr Fp& operator ++ () {
        ++val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -- () {
        if (val == 0) val += MOD;
        --val;
        return *this;
    }
    constexpr Fp operator ++ (int) const {
        Fp res = *this;
        ++*this;
        return res;
    }
    constexpr Fp operator -- (int) const {
        Fp res = *this;
        --*this;
        return res;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) {
        return os << x.val;
    }
    friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
        return r.pow(n);
    }
    friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {
        return r.inv();
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> X(M), Y(M), compr;
    for (int i = 0; i < M; i++) {
        cin >> X[i] >> Y[i], X[i]--, Y[i]--;
        compr.push_back(X[i]), compr.push_back(Y[i]);
    }
    compr.push_back(0);
    sort(compr.begin(), compr.end());
    compr.erase(unique(compr.begin(), compr.end()), compr.end());  

    // 新しいグラフ
    int V = compr.size();
    vector<vector<pair<int,int>>> G(V);
    if (V > 1) {
        for (int i = 0; i < V; i++) {
            int cur = compr[i], nex = compr[(i+1) % compr.size()];
            if (cur > nex) nex += N;
            G[i].emplace_back((i+1) % compr.size(), nex - cur);
        }
    } else G[0].emplace_back(0, N);
    for (int i = 0; i < M; i++) {
        int x = lower_bound(compr.begin(), compr.end(), X[i]) - compr.begin();
        int y = lower_bound(compr.begin(), compr.end(), Y[i]) - compr.begin();
        G[x].emplace_back(y, 1);
    }

    // DP
    vector dp(K+1, vector(V, mint(0)));
    dp[0][0] = 1;
    for (int k = 0; k <= K; k++) {
        for (int v = 0; v < V; v++) {
            for (auto [v2, add] : G[v]) {
                if (k + add <= K) dp[k+add][v2] += dp[k][v];
            }
        }
    }
    mint res = 0;
    for (int v = 0; v < V; v++) {
        res += dp[K][v];
        for (int k = 0; k < K; k++) {
            for (auto [v2, add] : G[v]) {
                if (k + add > K) res += dp[k][v];
            }
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 372 F - Teleporting Takahashi 2 (2D, 青色, 525 点)

問題概要

制約

考えたこと

コード