結果

問題 No.3315 FPS Game
コンテスト
ユーザー kidodesu
提出日時 2025-04-13 12:25:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,629 bytes
コンパイル時間 2,208 ms
コンパイル使用メモリ 205,680 KB
実行使用メモリ 33,060 KB
最終ジャッジ日時 2025-05-02 20:02:47
合計ジャッジ時間 14,677 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 TLE * 2 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int N = 1000000 + 10;

ll F[N], E[N];

ll modpow(ll a, ll b, ll mod = MOD) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        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;
}

vector<ll> make(const vector<ll>& A, const vector<ll>& B) {
    int x = A.size(), y = B.size();
    vector<ll> C(x + y - 1);
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j < y; ++j) {
            C[i + j] = (C[i + j] + A[i] * B[j]) % MOD;
        }
    }
    return C;
}

vector<int> A;
vector<ll> merge(int l, int r) {
    if (l == r) {
        int a = A[l];
        vector<ll> res(a + 1);
        for (int i = 0; i <= a; ++i) {
            res[i] = comb(a, i) * F[i] % MOD;
        }
        return res;
    }
    int mid = (l + r) / 2;
    return make(merge(l, mid), merge(mid + 1, r));
}

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

    F[0] = E[0] = 1;
    for (int i = 1; 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 >= 1; --i) E[i] = E[i + 1] * (i + 1) % MOD;

    int n, s, t;
    cin >> n >> s >> t;
    s--, t--;

    int M = 2 * n - 1;
    vector<vector<int>> node(M);
    vector<int> V(M, 0);

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

    vector<int> D(M, -1);
    queue<int> q;
    D[n + s] = 0;
    q.push(n + s);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nxt : node[cur]) {
            if (D[nxt] == -1) {
                D[nxt] = D[cur] + 1;
                q.push(nxt);
            }
        }
    }

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

    vector<ll> Ans;
    if (!A.empty()) {
        Ans = merge(0, A.size() - 1);
    }

    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