結果

問題 No.3315 FPS Game
コンテスト
ユーザー kidodesu
提出日時 2025-04-13 12:19:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,531 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 82,740 KB
実行使用メモリ 124,672 KB
最終ジャッジ日時 2025-05-02 20:02:57
合計ジャッジ時間 9,721 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353
N = 10 ** 6 + 2
F = [1] * N
E = [1] * N
for i in range(2, N):
    F[i] = F[i-1]*i%mod
E[-1] = pow(F[-1], -1, mod)
for i in range(N-1, 0, -1):
    E[i-1] = E[i]*i%mod

def comb(a, b):
    if b < 0:
        return 0
    if a < b:
        return 0
    return F[a] * E[b] * E[a-b] % mod

from collections import deque

n, s, t = map(int, input().split())
s, t = s-1, t-1
N = 2*n-1
node = [[] for _ in range(N)]

V = [0] * N
for i in range(n-1):
    u, v = [int(x)-1 for x in input().split()]
    node[u].append(n+i)
    node[v].append(n+i)
    node[n+i].append(u)
    node[n+i].append(v)
    V[u] += 1
    V[v] += 1
    V[n+i] += 2

D = [-1] * N
D[n+s] = 0
dq = deque([n+s])
while dq:
    now = dq.popleft()
    for nxt in node[now]:
        if D[nxt] == -1:
            D[nxt] = D[now] + 1
            dq.append(nxt)

A = []
now = n+t
cnt = 0
while now != n+s:
    if 0 <= now < n and V[now] >= 2:
        A.append(V[now]-2)
    if n <= now:
        cnt += 1
    for nxt in node[now]:
        if D[nxt] < D[now]:
            now = nxt
            break

def make(X, Y):
    x = len(X)
    y = len(Y)
    z = x + y - 1
    Z = [0] * z
    for i in range(x):
        for j in range(y):
            Z[i+j] += X[i] * Y[j] % mod; Z[i+j] %= mod
    return Z

def merge(l, r):
    if l == r:
        a = A[l]
        return [(comb(a, i) * F[i]) % mod for i in range(a+1)]
    mid = l + r >> 1
    return make(merge(l, mid), merge(mid + 1, r))

Ans = merge(0, len(A)-1)

print(* [0] * cnt + Ans + [0] * (n - len(Ans) - cnt))
0