結果

問題 No.2005 Sum of Power Sums
ユーザー lam6er
提出日時 2025-03-31 17:50:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,009 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 83,096 KB
実行使用メモリ 161,280 KB
最終ジャッジ日時 2025-03-31 17:51:13
合計ジャッジ時間 6,029 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1
    K = list(map(int, input[idx:idx + N]))
    idx += N
    
    max_k = max(K) if K else 0
    max_stirling = max_k
    max_N = N
    
    # Precompute Stirling numbers of the second kind
    stirling = [[0] * (max_stirling + 1) for _ in range(max_stirling + 1)]
    stirling[0][0] = 1
    for k in range(1, max_stirling + 1):
        for m in range(1, k + 1):
            stirling[k][m] = (stirling[k-1][m] * m + stirling[k-1][m-1]) % mod
    
    # Precompute factorials and inverse factorials up to max_r = 5000 + 2e5
    max_r = max_k + max_N
    fac = [1] * (max_r + 1)
    for i in range(1, max_r + 1):
        fac[i] = fac[i-1] * i % mod
    inv_fac = [1] * (max_r + 1)
    inv_fac[max_r] = pow(fac[max_r], mod-2, mod)
    for i in range(max_r-1, -1, -1):
        inv_fac[i] = inv_fac[i+1] * (i+1) % mod
    
    # Compute rem = (M + N) mod mod
    rem = (M % mod + N % mod) % mod
    
    # Precompute perm[r] = product_{i=0}^{r-1} (rem - i) mod mod for 0 <= r <= max_r
    max_perm_r = max_k + max_N
    perm = [1] * (max_perm_r + 1)
    for r in range(1, max_perm_r + 1):
        term = (rem - (r-1)) % mod
        perm[r] = perm[r-1] * term % mod
    
    # Compute the answer
    answer = 0
    for k in K:
        current_sum = 0
        for m in range(0, k+1):
            s = stirling[k][m]
            if s == 0:
                continue
            r = m + N
            if r > max_perm_r:
                c = 0
            else:
                numerator = perm[r]
                denom = inv_fac[r]
                c = numerator * denom % mod
                if r > rem:
                    c = 0
            term = s * fac[m] % mod
            term = term * c % mod
            current_sum = (current_sum + term) % mod
        answer = (answer + current_sum) % mod
    print(answer % mod)

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