結果

問題 No.3589 Make Ends Meet (Hard)
コンテスト
ユーザー marc2825
提出日時 2026-06-13 16:25:26
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 4,157 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 239 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 94,208 KB
最終ジャッジ日時 2026-07-10 21:01:07
合計ジャッジ時間 10,836 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys, numpy as np

def solve():
    N, M, K = map(int, sys.stdin.read().split())
    MOD = 998244353
    E = N*(N-1)//2          # 完全グラフの辺数
    target = E - M          # 残す辺数
    if target < 0:
        print(0); return
    Lv = E + 1              # y(=1+x) の指数ベクトル長
    NA = N - 2              # 無名頂点（1, N 以外）の数

    # 階乗・二項係数
    fact = [1]*(E+1)
    for i in range(1, E+1): fact[i] = fact[i-1]*i % MOD
    inv_fact = [1]*(E+1)
    inv_fact[E] = pow(fact[E], MOD-2, MOD)
    for i in range(E, 0, -1): inv_fact[i-1] = inv_fact[i]*i % MOD
    def binom(n, r):
        if r < 0 or r > n or n < 0: return 0
        return fact[n]*inv_fact[r] % MOD * inv_fact[n-r] % MOD

    # btt[x] = C(x, target)
    btt = np.array([binom(x, target) for x in range(Lv)], dtype=np.int64)

    def zeros(): return np.zeros(Lv, dtype=np.int64)
    def shift_add(dst, src, off, coef):     # dst[i+off] += src[i]*coef
        if coef == 0 or off >= Lv: return
        n = Lv - off
        dst[off:off+n] = (dst[off:off+n] + src[:n]*coef) % MOD
    def acc(d, key, vec):
        d[key] = (d[key] + vec) % MOD if key in d else vec % MOD

    # 無名頂点だけの層を1つ作る（≥1頂点）。incoming/戻り値: {(prev,used): vec}
    def build_anon(incoming):
        done = {}
        active = {}
        for (p, used), ev in incoming.items():
            rem = NA - used
            if rem <= 0: continue
            nv = zeros()
            shift_add(nv, ev, p, rem % MOD)         # +y^p
            shift_add(nv, ev, 0, (MOD-rem) % MOD)   # -y^0  → (y^p-1)*選択
            acc(active, (p, used+1), nv)
        j = 1
        while active:
            nxt = {}
            for (p, used), vec in active.items():
                acc(done, (j, used), (vec*inv_fact[j]) % MOD)   # サイズ j で確定
                rem = NA - used
                if rem > 0:                                     # 頂点を1つ追加
                    nv = zeros()
                    shift_add(nv, vec, p+j, rem % MOD)          # 前層へ≥1
                    shift_add(nv, vec, j, (MOD-rem) % MOD)      # 既存 j 頂点へ自由
                    acc(nxt, (p, used+1), nv)
            active = nxt; j += 1
        return done

    # 層K（頂点Nを強制配置 + 無名 c 個）
    def build_K(incoming):
        done = {}
        active = {}
        for (p, used), ev in incoming.items():      # まず N を置く
            nv = zeros()
            shift_add(nv, ev, p, 1)
            shift_add(nv, ev, 0, MOD-1)
            acc(active, (p, 1, used), nv)
        while active:
            nxt = {}
            for (p, size, used), vec in active.items():
                acc(done, (size, used), (vec*inv_fact[size-1]) % MOD)
                rem = NA - used
                if rem > 0:                          # 無名頂点を追加
                    nv = zeros()
                    shift_add(nv, vec, p+size, rem % MOD)
                    shift_add(nv, vec, size, (MOD-rem) % MOD)
                    acc(nxt, (p, size+1, used+1), nv)
            active = nxt
        return done

    ans = 0
    def finalize(states):       # 残りを未到達Uにして回収（U内部辺は自由）
        nonlocal ans
        for (p, used), vec in states.items():
            u = NA - used
            if u < 0: continue
            su = u*(u-1)//2     # C(u,2) 本の自由辺 = 指数シフト
            if su >= Lv: continue
            L2 = Lv - su
            prod = (vec[:L2] * btt[su:su+L2]) % MOD
            ans = (ans + int(prod.sum() % MOD)) % MOD

    e0 = zeros(); e0[0] = 1
    cur = {(1, 0): e0}                  # 層0 = {1}
    ok = True
    for _ in range(K-1):                # 層 1..K-1
        cur = build_anon(cur)
        if not cur: ok = False; break
    if ok and cur:
        sK = build_K(cur)               # 層 K
        finalize(sK)                    # T = K
        cur = sK
        while cur:                      # 層 K+1, K+2, ...
            cur = build_anon(cur)
            if not cur: break
            finalize(cur)
    print(ans % MOD)

solve()
0