結果

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

ソースコード

diff # 

MOD = 10**9 + 9

def main():
    import sys
    N = int(sys.stdin.readline().strip())

    # Precompute c_a = (a+1)^2 mod MOD for a from 1 to N
    c = [0] * (N + 2)
    for a in range(1, N + 1):
        c[a] = pow(a + 1, 2, MOD)
    
    # Precompute factorial and inverse factorial modulo MOD
    max_m = N
    fact = [1] * (max_m + 1)
    for i in range(1, max_m + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (max_m + 1)
    inv_fact[max_m] = pow(fact[max_m], MOD - 2, MOD)
    for i in range(max_m - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    
    # Function to compute the coefficients of S(x)^m up to x^K
    def compute_Sm(max_m):
        # S(x) = sum_{a=1}^N c[a] x^a
        Sm = [ [0]*(N+1) for _ in range(max_m + 1) ]
        Sm[0][0] = 1
        for m in range(1, max_m + 1):
            for k in range(N, -1, -1):
                if Sm[m-1][k] == 0:
                    continue
                for a in range(1, N+1):
                    if k + a > N:
                        continue
                    Sm[m][k + a] = (Sm[m][k + a] + Sm[m-1][k] * c[a]) % MOD
        return Sm
    # Compute S^m up to m = N
    Sm = compute_Sm(N)
    
    # Precompute the coefficients for cos(S) + sin(S)
    f = [0] * (N + 1)
    f[0] = 1  # cos(0) + sin(0) = 1
    for m in range(1, N + 1):
        sign = 1
        if m % 4 == 2 or m % 4 == 3:
            sign = -1
        am = sign * inv_fact[m]
        for k in range(m, N + 1):
            f[k] = (f[k] + am * Sm[m][k]) % MOD
    
    # Multiply by N! and take modulo
    N_fact = fact[N]
    for k in range(1, N + 1):
        f[k] = f[k] * N_fact % MOD
    
    for k in range(1, N + 1):
        print(f[k] % MOD)

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