結果

問題 No.1080 Strange Squared Score Sum
ユーザー gew1fw
提出日時 2025-06-12 17:10:48
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,504 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 848,848 KB
最終ジャッジ日時 2025-06-12 17:10:50
合計ジャッジ時間 2,520 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 9

def main():
    import sys
    N = int(sys.stdin.readline())
    
    # Precompute factorial and inverse factorial
    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i - 1] * i % MOD
    
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    
    # Compute G_x(t) = sum_{x=1 to N} (x+1)^2 * t^x
    # We need to compute coefficients up to t^N
    Gx = [0] * (N + 1)
    for x in range(1, N + 1):
        val = (x + 1) ** 2
        Gx[x] = val % MOD
    
    # Now, for each K, compute the contribution from M=0 to N
    # Using dynamic programming
    dp = [ [0]*(N+1) for _ in range(N+1) ]
    dp[0][0] = 1
    for M in range(1, N+1):
        for x in range(1, N+1):
            for k in range(x, N+1):
                dp[M][k] = (dp[M][k] + Gx[x] * dp[M-1][k - x]) % MOD
    
    # Now, for each K, compute the sum over M of (N! / M! ) * s(M) * dp[M][K]
    result = [0] * (N + 1)
    for K in range(1, N+1):
        total = 0
        for M in range(1, min(K, N) + 1):
            s = 1 if (M % 4) in {0, 1} else -1
            term = fact[N] * inv_fact[M] % MOD
            term = term * s % MOD
            term = term * dp[M][K] % MOD
            total = (total + term) % MOD
        result[K] = total
    
    for K in range(1, N+1):
        print(result[K] % MOD)

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