結果

問題 No.2005 Sum of Power Sums
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:46:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,661 bytes
コンパイル時間 513 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 282,372 KB
最終ジャッジ日時 2025-06-12 16:46:33
合計ジャッジ時間 6,089 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    K = list(map(int, sys.stdin.readline().split()))
    
    # Precompute Stirling numbers of the second kind up to K_i=5000
    max_K = max(K) if K else 0
    stirling = [[0] * (max_K + 1) for _ in range(max_K + 1)]
    stirling[0][0] = 1
    for n in range(1, max_K + 1):
        for k in range(1, n + 1):
            stirling[n][k] = (stirling[n-1][k] * k + stirling[n-1][k-1]) % MOD
    
    # Precompute factorials up to max_K
    fact = [1] * (max_K + 1)
    for i in range(1, max_K + 1):
        fact[i] = fact[i-1] * i % MOD
    
    a = M + N
    max_k_needed = max(K) if K else 0
    c = [0] * (max_k_needed + 1)
    
    for k in range(max_k_needed + 1):
        b = N + k
        a_mod = a % MOD
        b_mod = b % MOD
        if a_mod < b_mod:
            c[k] = 0
        else:
            numerator = 1
            for i in range(b_mod):
                numerator = numerator * (a_mod - i) % MOD
            denominator = 1
            for i in range(1, b_mod + 1):
                denominator = denominator * i % MOD
            inv_denominator = pow(denominator, MOD - 2, MOD)
            c[k] = numerator * inv_denominator % MOD
    
    total = 0
    for k_i in K:
        res = 0
        for k in range(k_i + 1):
            s = stirling[k_i][k] if k <= k_i else 0
            fk = fact[k] if k <= max_K else 0
            term = s * fk % MOD
            term = term * c[k] % MOD
            res = (res + term) % MOD
        total = (total + res) % MOD
    print(total % MOD)

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