#1168735 (PyPy3) No.3589 Make Ends Meet (Hard)

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-06-09 12:57:06
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,153 ms / 2,000 ms
• コード長: 3,959 bytes
• コンパイル時間: 265 ms
• コンパイル使用メモリ: 95,852 KB
• 実行使用メモリ: 102,912 KB
• 最終ジャッジ日時: 2026-07-10 21:00:22
• 合計ジャッジ時間: 8,734 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

MOD = 998244353

def modpow(a, e):
    r = 1
    while e:
        if e & 1:
            r = r * a % MOD
        a = a * a % MOD
        e >>= 1
    return r

def poly_mul(a, b, D):
    """
    Multiply two polynomials modulo x^(D+1).
    """
    if not a or not b:
        return []

    n = len(a)
    m = len(b)
    L = min(D + 1, n + m - 1)

    res = [0] * L

    for i in range(n):
        ai = a[i]
        if ai == 0:
            continue

        max_j = min(m, D + 1 - i)
        for j in range(max_j):
            res[i + j] = (res[i + j] + ai * b[j]) % MOD

    return res

def poly_add_to(dst, src, scale):
    """
    dst += scale * src
    """
    if not src or scale == 0:
        return

    if len(dst) < len(src):
        dst.extend([0] * (len(src) - len(dst)))

    for i, v in enumerate(src):
        dst[i] = (dst[i] + scale * v) % MOD


N, M, K = map(int, input().split())

E = N * (N - 1) // 2
R = E - M
S = N - 2

# We only need coefficients up to x^R.
D = R

# Binomial coefficients.
# Need up to max(E, N), because we use (1+x)^m where m can be E,
# and also choose ordinary vertices up to N.
MAX = max(E, N)

C = [[0] * (MAX + 1) for _ in range(MAX + 1)]
for i in range(MAX + 1):
    C[i][0] = 1
    C[i][i] = 1
    for j in range(1, i):
        C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD

def nCr(n, r):
    if r < 0 or r > n:
        return 0
    return C[n][r]

# one_plus_pow[m] = (1+x)^m, truncated to degree D.
one_plus_pow = [[] for _ in range(MAX + 1)]
for m in range(MAX + 1):
    one_plus_pow[m] = [nCr(m, i) for i in range(min(D, m) + 1)]


# Precompute:
# trans[b][c] = ((1+x)^b - 1)^c * (1+x)^{c choose 2}
#
# b = previous layer size
# c = next layer size
max_layer_size = N
trans = [[[] for _ in range(max_layer_size + 1)] for _ in range(max_layer_size + 1)]

for b in range(max_layer_size + 1):
    base = one_plus_pow[b][:]      # (1+x)^b
    base[0] = (base[0] - 1) % MOD  # (1+x)^b - 1

    power = [1]  # base^0

    for c in range(max_layer_size + 1):
        if c > 0:
            power = poly_mul(power, base, D)

        inside_edges = c * (c - 1) // 2
        trans[b][c] = poly_mul(power, one_plus_pow[inside_edges], D)


# dp[a][b]:
# a = number of ordinary vertices already placed in L_1,...,L_j
# b = size of current layer L_j
#
# Initially, L_0 = {1}.
dp = [[[] for _ in range(max_layer_size + 1)] for _ in range(S + 1)]
dp[0][1] = [1]

for j in range(K):
    ndp = [[[] for _ in range(max_layer_size + 1)] for _ in range(S + 1)]

    is_last_layer = (j + 1 == K)

    for a in range(S + 1):
        remaining = S - a

        for b in range(max_layer_size + 1):
            p = dp[a][b]
            if not p:
                continue

            if not is_last_layer:
                # L_{j+1} consists only of ordinary vertices.
                # Its size c must be at least 1.
                for c in range(1, remaining + 1):
                    ways = nCr(remaining, c)
                    a2 = a + c

                    tmp = poly_mul(p, trans[b][c], D)
                    poly_add_to(ndp[a2][c], tmp, ways)

            else:
                # L_K must contain vertex N.
                # If |L_K| = c, then c-1 ordinary vertices are chosen.
                for c in range(1, remaining + 2):
                    ways = nCr(remaining, c - 1)
                    a2 = a + (c - 1)

                    tmp = poly_mul(p, trans[b][c], D)
                    poly_add_to(ndp[a2][c], tmp, ways)

    dp = ndp


# Final contribution from T:
# T has remaining ordinary vertices.
# Edges between L_K and T, and inside T, are free.
ans = 0

for a in range(S + 1):
    remaining = S - a

    for b in range(max_layer_size + 1):
        p = dp[a][b]
        if not p:
            continue

        free_edges = remaining * b + remaining * (remaining - 1) // 2
        tmp = poly_mul(p, one_plus_pow[free_edges], D)

        if R < len(tmp):
            ans += tmp[R]
            ans %= MOD

print(ans)