結果

問題 No.1080 Strange Squared Score Sum
ユーザー qwewe
提出日時 2025-05-14 12:56:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,161 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 56,396 KB
最終ジャッジ日時 2025-05-14 12:58:03
合計ジャッジ時間 7,416 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 9

def main():
    import sys
    N, = map(int, sys.stdin.read().split())
    
    # Precompute factorial and inverse factorial modulo MOD
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (N + 1)
    inv_fact[N] = pow(fact[N], MOD-2, MOD)
    for i in range(N-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    # Find a square root of -1 mod MOD using the fact that MOD ≡ 1 mod 4
    # Using Tonelli-Shanks algorithm to find sqrt(-1)
    def tonelli_shanks(n, p):
        if pow(n, (p-1)//2, p) != 1:
            return None
        Q = p - 1
        S = 0
        while Q % 2 == 0:
            Q //= 2
            S += 1
        z = 2
        while pow(z, (p-1)//2, p) != p-1:
            z += 1
        c = pow(z, Q, p)
        x = pow(n, (Q+1)//2, p)
        t = pow(n, Q, p)
        m = S
        while t != 1:
            i, temp = 0, t
            while temp != 1 and i < m:
                temp = pow(temp, 2, p)
                i += 1
            if i == m:
                return None
            b = pow(c, 1 << (m - i - 1), p)
            x = x * b % p
            t = t * b * b % p
            c = b * b % p
            m = i
        return x
    sqrt_neg_1 = tonelli_shanks(MOD-1, MOD)
    i = sqrt_neg_1
    
    # Compute f(x) = sum_{a=1 to N} (a+1)^2 x^a
    f_coeff = [0] * (N+1)
    for a in range(1, N+1):
        if a > N:
            break
        val = (a + 1) * (a + 1) % MOD
        f_coeff[a] = val
    
    # Compute H(x) = cos(f(x)) + sin(f(x)) mod x^{N+1}
    # Using the series expansion up to terms that contribute to x^N
    # H(x) = sum_{m=0 to N} [ (-1)^{floor(m/2)} * f(x)^m / m! ]
    H = [0] * (N+1)
    H[0] = 1  # Initial term for m=0
    
    # Precompute the powers of f(x) using dynamic programming
    # dp[m][k] is the coefficient of x^k in f(x)^m
    # Instead, we use a rolling approach
    from collections import defaultdict
    current_pows = [0]*(N+1)
    current_pows[0] = 1  # f^0 is 1
    
    for m in range(1, N+1):
        next_pow = [0]*(N+1)
        # Multiply current_pows by f_coeff
        for k in range(N+1):
            if current_pows[k] == 0:
                continue
            for a in range(1, N+1):
                if k + a > N:
                    break
                next_pow[k+a] = (next_pow[k+a] + current_pows[k] * f_coeff[a]) % MOD
        current_pows = next_pow
        
        # Determine the sign: (-1)^{floor(m/2)}
        sign = -1 if (m // 2) % 2 else 1
        if m % 2 == 1:
            sign *= (-1 if (m//2) % 2 else 1)
        sign = (-1) ** (m // 2)
        if m % 2 == 1:
            sign *= 1
        
        # Add to H with division by m!
        inv_m_fact = inv_fact[m]
        term = sign * inv_m_fact % MOD
        for k in range(N+1):
            if k > N:
                break
            contrib = current_pows[k] * term % MOD
            H[k] = (H[k] + contrib) % MOD
    
    # Multiply by N! and handle modulo
    N_fact = fact[N]
    for K in range(1, N+1):
        res = H[K] * N_fact % MOD
        print(res)
    
if __name__ == '__main__':
    main()
0