結果

問題 No.3315 FPS Game
コンテスト
ユーザー kidodesu
提出日時 2025-04-13 15:08:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,380 bytes
コンパイル時間 2,198 ms
コンパイル使用メモリ 207,356 KB
実行使用メモリ 40,196 KB
最終ジャッジ日時 2025-05-02 20:03:02
合計ジャッジ時間 8,386 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MOD = 998244353;
const int N = 1e6 + 2;

vector<ll> F(N, 1), E(N, 1);

ll modpow(ll a, ll b, ll m = MOD) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll comb(int a, int b) {
    if (b < 0 || a < b) return 0;
    return F[a] * E[b] % MOD * E[a - b] % MOD;
}

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

    for (int i = 2; i < N; ++i) {
        F[i] = F[i - 1] * i % MOD;
    }
    E[N - 1] = modpow(F[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i) {
        E[i] = E[i + 1] * (i + 1) % MOD;
    }

    int n, s, t;
    cin >> n >> s >> t;
    --s; --t;
    int NN = 2 * n - 1;

    vector<vector<int>> node(NN);
    vector<int> V(NN);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        int p = n + i;
        node[u].push_back(p);
        node[v].push_back(p);
        node[p].push_back(u);
        node[p].push_back(v);
        V[u]++;
        V[v]++;
        V[p] += 2;
    }

    vector<int> D(NN, -1);
    deque<int> dq;
    D[n + s] = 0;
    dq.push_back(n + s);
    while (!dq.empty()) {
        int now = dq.front(); dq.pop_front();
        for (int nxt : node[now]) {
            if (D[nxt] == -1) {
                D[nxt] = D[now] + 1;
                dq.push_back(nxt);
            }
        }
    }

    vector<int> A;
    int now = n + t;
    int cnt = 0;
    while (now != n + s) {
        if (0 <= now && now < n && V[now] > 2) {
            A.push_back(V[now] - 2);
        }
        if (n <= now) cnt++;
        for (int nxt : node[now]) {
            if (D[nxt] < D[now]) {
                now = nxt;
                break;
            }
        }
    }

    vector<ll> Ans = {1};
    int l = 1;
    for (int a : A) {
        vector<ll> newAns(l + a, 0);
        for (int i = 0; i < l; ++i) {
            for (int j = 0; j <= a; ++j) {
                newAns[i + j] = (newAns[i + j] + Ans[i] * comb(a, j) % MOD * F[j] % MOD) % MOD;
            }
        }
        l += a;
        Ans = newAns;
    }

    for (int i = 0; i < cnt; ++i) cout << 0 << " ";
    for (ll x : Ans) cout << x << " ";
    for (int i = 0; i < n - (int)Ans.size() - cnt; ++i) cout << 0 << " ";
    cout << "\n";
    return 0;
}
0