Day 179-Q4 — 2026-10-15 | 最小 s-t カットの個数（最大流の残余グラフで「閉じた集合」を数える。強連結成分の DAG の順序イデアルの数え上げは #P 困難なので、成分ごとの積と分岐のメモ化で数える）

📋 コピーimport sys
from collections import deque


def max_flow(n, edges, s, t):
    """Dinic。残余容量つきの隣接リスト (to, cap, rev) を返す"""
    g = [[] for _ in range(n)]
    for u, v, c in edges:
        g[u].append([v, c, len(g[v])])
        g[v].append([u, 0, len(g[u]) - 1])
    flow = 0
    while True:
        level = [-1] * n
        level[s] = 0
        dq = deque([s])
        while dq:
            u = dq.popleft()
            for v, c, _ in g[u]:
                if c > 0 and level[v] < 0:
                    level[v] = level[u] + 1
                    dq.append(v)
        if level[t] < 0:
            return flow, g
        it = [0] * n

        def dfs(u, f):
            if u == t:
                return f
            while it[u] < len(g[u]):
                e = g[u][it[u]]
                v, c, r = e
                if c > 0 and level[v] == level[u] + 1:
                    d = dfs(v, min(f, c))
                    if d:
                        e[1] -= d
                        g[v][r][1] += d
                        return d
                it[u] += 1
            return 0

        while True:
            f = dfs(s, 1 << 62)
            if not f:
                break
            flow += f


def scc(n, adj):
    """Tarjan（反復）。comp[v] を返す"""
    index = [0] * n
    low = [0] * n
    onst = [False] * n
    comp = [-1] * n
    st = []
    cnt = 1
    nc = 0
    for r in range(n):
        if index[r]:
            continue
        work = [(r, 0)]
        index[r] = low[r] = cnt; cnt += 1
        st.append(r); onst[r] = True
        while work:
            u, i = work[-1]
            if i < len(adj[u]):
                work[-1] = (u, i + 1)
                v = adj[u][i]
                if not index[v]:
                    index[v] = low[v] = cnt; cnt += 1
                    st.append(v); onst[v] = True
                    work.append((v, 0))
                elif onst[v]:
                    low[u] = min(low[u], index[v])
            else:
                work.pop()
                if work:
                    p = work[-1][0]
                    low[p] = min(low[p], low[u])
                if low[u] == index[u]:
                    while True:
                        w = st.pop(); onst[w] = False
                        comp[w] = nc
                        if w == u:
                            break
                    nc += 1
    return nc, comp


def main():
    data = sys.stdin.buffer.read().split()
    n, m, s, t = (int(x) for x in data[:4])
    s -= 1; t -= 1
    edges = []
    for i in range(m):
        u, v, c = (int(x) for x in data[4 + 3 * i:7 + 3 * i])
        edges.append((u - 1, v - 1, c))
    flow, g = max_flow(n, edges, s, t)
    # 残余グラフ: 容量の残る辺 u->v。S が最小カット ⇔ s∈S, t∉S, S が残余辺で閉じている
    radj = [[v for v, c, _ in g[u] if c > 0] for u in range(n)]
    nc, comp = scc(n, radj)
    succ = [0] * nc                    # 成分 DAG の「到達できる成分」のビット集合（推移閉包）
    direct = [0] * nc
    for u in range(n):
        for v in radj[u]:
            if comp[u] != comp[v]:
                direct[comp[u]] |= 1 << comp[v]
    # Tarjan の成分番号は逆トポロジカル順（後続が小さい番号）なので小さい順に閉包を作れる
    for c in range(nc):
        r = 1 << c
        d = direct[c]
        while d:
            b = d & -d
            r |= succ[b.bit_length() - 1]
            d ^= b
        succ[c] = r
    pred = [0] * nc
    for c in range(nc):
        x = succ[c]
        while x:
            b = x & -x
            pred[b.bit_length() - 1] |= 1 << c
            x ^= b
    cs, ct = comp[s], comp[t]
    forced_in = succ[cs]               # s から届く成分は必ず S
    forced_out = pred[ct]              # t へ届く成分は必ず T
    free = ((1 << nc) - 1) & ~forced_in & ~forced_out
    nb = [succ[c] | pred[c] for c in range(nc)]   # 比較可能な成分（連結成分分けに使う）

    sys.setrecursionlimit(10000)
    memo = {}

    def count(mask):
        """mask 内の成分について「後続で閉じた部分集合」の数"""
        if mask == 0:
            return 1
        if mask in memo:
            return memo[mask]
        # 比較可能性で連結成分に分け、独立なら積
        low = mask & -mask
        comp_mask = low
        frontier = low
        while frontier:
            b = frontier & -frontier
            frontier ^= b
            nxt = nb[b.bit_length() - 1] & mask & ~comp_mask
            comp_mask |= nxt
            frontier |= nxt
        if comp_mask != mask:
            res = count(comp_mask) * count(mask & ~comp_mask)
        else:
            # 比較可能な相手が最も多い成分 v で場合分け
            best, bv = -1, 0
            x = mask
            while x:
                b = x & -x
                x ^= b
                c = b.bit_length() - 1
                k = (nb[c] & mask).bit_count()
                if k > best:
                    best, bv = k, c
            res = count(mask & ~succ[bv]) + count(mask & ~pred[bv])
            # v∈S なら後続すべて S（決まったので除く）、v∉S なら先行すべて T
        memo[mask] = res
        return res

    print(flow)
    print(count(free))


main()