結果
| 問題 | No.3828 Push, if Possible |
| コンテスト | |
| ユーザー |
Rho
|
| 提出日時 | 2026-11-10 13:52:18 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 4,296 ms / 5,000 ms |
| + 403µs | |
| コード長 | 5,822 bytes |
| 記録 | |
| コンパイル時間 | 87 ms |
| コンパイル使用メモリ | 65,272 KB |
| 実行使用メモリ | 115,500 KB |
| 最終ジャッジ日時 | 2026-11-22 12:40:51 |
| 合計ジャッジ時間 | 44,451 ms |
|
ジャッジサーバーID (参考情報) |
judge6_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 19 |
ソースコード
import sys
import threading
MOD = 998244353
def inv(x):
return pow(x % MOD, MOD - 2, MOD)
def set_stirling(n):
res = [0, 1]
for i in range(1, n):
res.append(0)
for j in range(i, -1, -1):
res[j + 1] = res[j]
for j in range(i + 1):
res[j] = (res[j] - i * res[j + 1]) % MOD
return res
def integral_matrix(n):
W = [[0] * n for _ in range(n)]
# Stirling number -> matrix W
Q = set_stirling(n)
invk = [inv(k + 1) for k in range(n)]
# coef[a][k] = a^(k+1) / (k+1)
coef = []
for a in range(n):
row = [0] * n
pw = a % MOD
for k in range(n):
row[k] = pw * invk[k] % MOD
pw = pw * a % MOD
coef.append(row)
for i in range(n):
R = [0] * n
R[n - 1] = Q[n]
for k in range(n - 1, 0, -1):
R[k - 1] = (Q[k] + i * R[k]) % MOD
denom = 1
for j in range(n):
if j != i:
denom = denom * (i - j) % MOD
c = inv(denom)
R = [r * c % MOD for r in R]
for a in range(n):
ca = coef[a]
W[a][i] = sum(R[k] * ca[k] for k in range(n)) % MOD
return W
def apply_mat(W, p):
return [sum(wij * pj for wij, pj in zip(row, p)) % MOD for row in W]
def solve(n, s, edges):
# graph[v] = [(to, id)] A->B なら 2i, B->A なら 2i+1
graph = [[] for _ in range(n)]
for i, (a, b) in enumerate(edges):
graph[a].append((b, 2 * i + 1))
graph[b].append((a, 2 * i))
W = integral_matrix(n)
WT = [[W[a][j] for a in range(n)] for j in range(n)] # WT[j][a] = W[a][j]
F = [None] * (2 * n)
G = [None] * (2 * n)
H = [None] * (2 * n)
D = [None] * (2 * n)
def setF(id_, f):
F[id_] = f
to_is_A = id_ & 1
G[id_] = apply_mat(W, f)
if to_is_A:
H[id_] = G[id_]
D[id_] = F[id_]
else:
g = G[id_]
H[id_] = [(t - g[t]) % MOD for t in range(n)]
D[id_] = [0] * n
def process(now, ids, targets):
T = len(targets)
d = len(ids)
out = [[0] * n for _ in range(T)]
is_x = s[now] == 'x'
Hs = [H[x] for x in ids]
Ds = [D[x] for x in ids]
rn = range(n)
ones = [1] * n
zeros = [0] * n
for j in rn:
Dj = [Ds[i][j] for i in range(d)]
L = []
for i in range(d):
h = Hs[i]
c = 1 + h[j]
L.append([(c - h[t]) % MOD for t in rn])
preP = [None] * (d + 1)
preK = [None] * (d + 1)
sufP = [None] * (d + 1)
sufK = [None] * (d + 1)
preP[0] = ones
preK[0] = zeros
sufP[d] = ones
sufK[d] = zeros
for i in range(d):
Li = L[i]
pp = preP[i]
pk = preK[i]
dj = Dj[i]
preP[i + 1] = [pp[t] * Li[t] % MOD for t in rn]
preK[i + 1] = [(pk[t] * Li[t] + dj * pp[t]) % MOD for t in rn]
for i in range(d - 1, -1, -1):
Li = L[i]
sp = sufP[i + 1]
sk = sufK[i + 1]
dj = Dj[i]
sufP[i] = [Li[t] * sp[t] % MOD for t in rn]
sufK[i] = [(sk[t] * Li[t] + dj * sp[t]) % MOD for t in rn]
wj = WT[j]
for k in range(T):
x = targets[k]
if x < 0:
P = preP[d]
K = preK[d]
else:
pp = preP[x]
pk = preK[x]
sp = sufP[x + 1]
sk = sufK[x + 1]
P = [pp[a] * sp[a] % MOD for a in rn]
K = [(pk[a] * sp[a] + sk[a] * pp[a]) % MOD for a in rn]
o = out[k]
if j == 0 and is_x:
out[k] = [(o[a] + wj[a] * K[a] + P[a]) % MOD for a in rn]
else:
out[k] = [(o[a] + wj[a] * K[a]) % MOD for a in rn]
return out
def dfs_down(now, par):
ids = []
peid = -1
for to, eid in graph[now]:
if to == par:
peid = eid ^ 1
continue
dfs_down(to, now)
ids.append(eid)
if par != -1:
setF(peid, process(now, ids, [-1])[0])
def dfs_up(now, par):
ids = []
targets = []
outs = []
for to, eid in graph[now]:
ids.append(eid)
if to != par:
targets.append(len(ids) - 1)
outs.append(eid ^ 1)
out = process(now, ids, targets)
for k in range(len(targets)):
setF(outs[k], out[k])
for to, _ in graph[now]:
if to != par:
dfs_up(to, now)
dfs_down(0, -1)
dfs_up(0, -1)
ans = 0
if n >= 2:
w1 = W[1]
for i in range(n - 1):
f0 = F[2 * i]
f1 = F[2 * i + 1]
for j in range(n):
ans = (ans + w1[j] * (1 - f0[j]) * f1[j]) % MOD
for i in range(1, n):
ans = ans * i % MOD
return ans
def main():
data = sys.stdin.buffer.read().split()
pos = 0
t = int(data[pos]); pos += 1
res = []
for _ in range(t):
n = int(data[pos]); pos += 1
s = data[pos].decode(); pos += 1
edges = []
for _ in range(n - 1):
a = int(data[pos]) - 1
b = int(data[pos + 1]) - 1
pos += 2
edges.append((a, b))
res.append(solve(n, s, edges))
print("\n".join(map(str, res)))
sys.setrecursionlimit(1 << 20)
threading.stack_size(1 << 27)
th = threading.Thread(target=main)
th.start()
th.join()
Rho