結果

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

ソースコード

diff #
raw source code 

import sys

MOD = 998244353

def solve():
    N, M, K = map(int, sys.stdin.read().split())

    E = N * (N - 1) // 2
    target = E - M
    if target < 0:
        print(0)
        return

    Lv = E + 1
    NA = N - 2

    # 階乗・二項係数
    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 = [binom(x, target) for x in range(Lv)]

    def zeros():
        return [0] * Lv

    def shift_add(dst, src, off, coef):
        """
        dst[i + off] += src[i] * coef
        """
        if coef == 0 or off >= Lv:
            return

        n = Lv - off
        mod = MOD

        # coef = 1 は頻出なので特殊化
        if coef == 1:
            for i in range(n):
                j = i + off
                v = dst[j] + src[i]
                if v >= mod:
                    v -= mod
                dst[j] = v

        # coef = -1 mod MOD も頻出なので特殊化
        elif coef == mod - 1:
            for i in range(n):
                j = i + off
                v = dst[j] - src[i]
                if v < 0:
                    v += mod
                dst[j] = v

        else:
            c = coef
            for i in range(n):
                j = i + off
                v = dst[j] + src[i] * c % mod
                if v >= mod:
                    v -= mod
                dst[j] = v

    def add_vec(dst, src):
        mod = MOD
        for i in range(Lv):
            v = dst[i] + src[i]
            if v >= mod:
                v -= mod
            dst[i] = v

    def mul_vec(src, coef):
        if coef == 1:
            return src[:]
        mod = MOD
        return [(x * coef) % mod for x in src]

    def acc(d, key, vec):
        if key in d:
            add_vec(d[key], vec)
        else:
            d[key] = vec

    # 無名頂点だけの層を1つ作る
    # incoming / return: {(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)
            shift_add(nv, ev, 0, (MOD - rem) % MOD)
            acc(active, (p, used + 1), nv)

        j = 1
        while active:
            nxt = {}
            invj = inv_fact[j]

            for (p, used), vec in active.items():
                acc(done, (j, used), mul_vec(vec, invj))

                rem = NA - used
                if rem > 0:
                    nv = zeros()
                    shift_add(nv, vec, p + j, rem % MOD)
                    shift_add(nv, vec, j, (MOD - rem) % MOD)
                    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():
            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), mul_vec(vec, inv_fact[size - 1]))

                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):
        nonlocal ans

        for (_p, used), vec in states.items():
            u = NA - used
            if u < 0:
                continue

            su = u * (u - 1) // 2
            if su >= Lv:
                continue

            L2 = Lv - su
            s = 0
            for i in range(L2):
                if vec[i]:
                    s += vec[i] * btt[su + i]
                    s %= MOD

            ans += s
            ans %= 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)


if __name__ == "__main__":
    solve()
0