結果

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

ソースコード

diff #
raw source code 

MOD = 998244353

def poly_mul(a, b, E):
    res = [0] * (E + 1)

    for i in range(E + 1):
        for j in range(E + 1 - i):
            res[i + j] = (res[i + j] + a[i] * b[j]) % MOD

    return res

def poly_add_scaled(dst, src, scale, E):
    for i in range(E + 1):
        dst[i] = (dst[i] + src[i] * scale) % MOD


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

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

# 無効状態まで全部回すため、free_edges が E を超える場合にも壊れないようにする
max_free_edges = S * N + S * (S - 1) // 2
MAX = max(E, max_free_edges)

# binomial coefficients
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
# ただし多項式としては x^E までだけ持つ
one_plus_pow = [[0] * (E + 1) for _ in range(MAX + 1)]

for m in range(MAX + 1):
    for i in range(min(E, m) + 1):
        one_plus_pow[m][i] = nCr(m, i)


# trans[b][c] =
# ((1+x)^b - 1)^c * (1+x)^{c(c-1)/2}
trans = [[None for _ in range(N + 1)] for _ in range(N + 1)]

for b in range(N + 1):
    base = one_plus_pow[b][:]
    base[0] -= 1
    base[0] %= MOD

    power = [0] * (E + 1)
    power[0] = 1

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

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


# dp[a][b]:
# a = L_1,...,L_j に使った普通頂点数
# b = 現在の BFS 層 L_j のサイズ
dp = [[[0] * (E + 1) for _ in range(N + 1)] for _ in range(S + 1)]

# L_0 = {1}
dp[0][1][0] = 1

for j in range(K):
    ndp = [[[0] * (E + 1) for _ in range(N + 1)] for _ in range(S + 1)]

    last = (j + 1 == K)

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

        for b in range(N + 1):
            if not last:
                # L_{j+1} は普通頂点だけからなる
                for c in range(1, rem + 1):
                    ways = nCr(rem, c)
                    a2 = a + c

                    tmp = poly_mul(dp[a][b], trans[b][c], E)
                    poly_add_scaled(ndp[a2][c], tmp, ways, E)

            else:
                # L_K は頂点 N を必ず含む
                # |L_K| = c なら、普通頂点を c-1 個選ぶ
                for c in range(1, rem + 2):
                    ways = nCr(rem, c - 1)
                    a2 = a + c - 1

                    tmp = poly_mul(dp[a][b], trans[b][c], E)
                    poly_add_scaled(ndp[a2][c], tmp, ways, E)

    dp = ndp


ans = 0

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

    for b in range(N + 1):
        free_edges = rem * b + rem * (rem - 1) // 2

        tmp = poly_mul(dp[a][b], one_plus_pow[free_edges], E)

        ans += tmp[R]
        ans %= MOD

print(ans)
0