結果

問題 No.3828 Push, if Possible
コンテスト
ユーザー Rho
提出日時 2026-11-10 13:51:56
言語 Python3
(3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 5,822 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 62 ms
コンパイル使用メモリ 15,232 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2026-11-22 12:40:06
合計ジャッジ時間 9,679 ms
ジャッジサーバーID
(参考情報)
judge5_0 / judge6_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

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()
0