結果

問題 No.3589 Make Ends Meet (Hard)
コンテスト
ユーザー marc2825
提出日時 2026-05-29 17:31:42
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,135 ms / 2,000 ms
コード長 3,003 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 225 ms
コンパイル使用メモリ 96,356 KB
実行使用メモリ 86,428 KB
最終ジャッジ日時 2026-07-10 20:55:55
合計ジャッジ時間 12,276 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Alternative solution: evaluate the generating polynomial at x=0..E and interpolate.
# Complexity: O(N^6), PyPy3 reference.
MOD = 998244353

def main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    E = N * (N - 1) // 2
    R = E - M
    S = N - 2

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

    def eval_at(x):
        q = x + 1
        if q >= MOD:
            q -= MOD
        qpow = [1] * (E + 1)
        for i in range(1, E + 1):
            qpow[i] = qpow[i - 1] * q % MOD

        wpow = [[1] * (S + 1) for _ in range(S + 2)]
        for s in range(S + 2):
            w = qpow[s] - 1
            if w < 0:
                w += MOD
            for t in range(1, S + 1):
                wpow[s][t] = wpow[s][t - 1] * w % MOD

        dp = [[0] * (S + 2) for _ in range(S + 1)]
        dp[S][1] = 1
        for _ in range(K - 1):
            ndp = [[0] * (S + 2) for _ in range(S + 1)]
            for r in range(S + 1):
                row = dp[r]
                for s, cur in enumerate(row):
                    if cur == 0:
                        continue
                    for t in range(r + 1):
                        add = cur * C[r][t] % MOD
                        add = add * wpow[s][t] % MOD
                        add = add * qpow[t * (t - 1) // 2] % MOD
                        ndp[r - t][t] += add
                        if ndp[r - t][t] >= MOD:
                            ndp[r - t][t] -= MOD
            dp = ndp

        ans = 0
        for r in range(S + 1):
            for s, cur in enumerate(dp[r]):
                if cur == 0:
                    continue
                factor = qpow[s] - 1
                if factor < 0:
                    factor += MOD
                base = s * r + r + r * (r - 1) // 2
                ans = (ans + cur * factor % MOD * qpow[base]) % MOD
        return ans

    vals = [eval_at(x) for x in range(E + 1)]

    # Newton interpolation at 0,1,...,E.
    # P(x)=sum_k diff[k] * C(x,k), where diff[k]=Delta^k P(0).
    diff = vals[:]
    for k in range(E + 1):
        for i in range(E, k, -1):
            diff[i] -= diff[i - 1]
            if diff[i] < 0:
                diff[i] += MOD

    inv = [1] * (E + 2)
    for i in range(1, E + 2):
        inv[i] = pow(i, MOD - 2, MOD)

    basis = [1]  # binom(x, 0)
    ans = 0
    for k in range(E + 1):
        if R < len(basis):
            ans = (ans + diff[k] * basis[R]) % MOD
        if k == E:
            break
        nbasis = [0] * (len(basis) + 1)
        for i, v in enumerate(basis):
            nbasis[i] = (nbasis[i] - v * k) % MOD
            nbasis[i + 1] = (nbasis[i + 1] + v) % MOD
        invk = inv[k + 1]
        for i in range(len(nbasis)):
            nbasis[i] = nbasis[i] * invk % MOD
        basis = nbasis

    print(ans)

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