結果

問題 No.1080 Strange Squared Score Sum
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:25:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,672 bytes
コンパイル時間 1,079 ms
コンパイル使用メモリ 78,424 KB
実行使用メモリ 12,196 KB
最終ジャッジ日時 2025-05-14 13:27:15
合計ジャッジ時間 7,385 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 1000000009;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 1000000009;
        base = (base * base) % 1000000009;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 1000000009 - 2);
}

const int MOD = 1000000009;

struct Complex {
    long long re, im;
    Complex(long long r = 0, long long i = 0) : re(r), im(i) {}

    Complex operator+(const Complex& other) const {
        return Complex((re + other.re) % MOD, (im + other.im) % MOD);
    }
    Complex operator-(const Complex& other) const {
        return Complex((re - other.re + MOD) % MOD, (im - other.im + MOD) % MOD);
    }
    Complex operator*(const Complex& other) const {
        long long r_part = (re * other.re) % MOD;
        long long i_part = (im * other.im) % MOD;
        long long cross1 = (re * other.im) % MOD;
        long long cross2 = (im * other.re) % MOD;
        return Complex((r_part - i_part + MOD) % MOD, (cross1 + cross2) % MOD);
    }
    Complex operator*(long long scalar) const { // scalar multiplication by real
        return Complex((re * scalar) % MOD, (im * scalar) % MOD);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    std::cin >> N;

    if (N == 0) return 0;

    std::vector<long long> p_prime_coeffs(N + 1); // P'_j = (j+1)(j+2)^2
    for (int j = 0; j < N; ++j) { // P'(z) has terms up to z^(N-1) if P(z) is infinite
                                 // or min(N-1, deg(P)-1) if P(z) is polynomial
        long long j_plus_1 = j + 1;
        long long j_plus_2 = j + 2;
        p_prime_coeffs[j] = (j_plus_1 * j_plus_2 % MOD * j_plus_2 % MOD) % MOD;
    }

    std::vector<Complex> E(N + 1);
    E[0] = Complex(1, 0); // E_0 = 1

    Complex I(0, 1);

    for (int k = 1; k <= N; ++k) {
        Complex sum_val(0, 0);
        for (int j = 0; j < k; ++j) {
            // P'_j * E_{k-1-j}
            Complex term = E[k - 1 - j] * p_prime_coeffs[j];
            sum_val = sum_val + term;
        }
        E[k] = (I * sum_val) * modInverse(k);
    }

    std::vector<long long> f(N + 1);
    for (int k = 1; k <= N; ++k) {
        f[k] = (E[k].re + E[k].im) % MOD;
        if (f[k] < 0) f[k] += MOD;
    }

    long long N_factorial = 1;
    for (int i = 1; i <= N; ++i) {
        N_factorial = (N_factorial * i) % MOD;
    }
    
    for (int k = 1; k <= N; ++k) {
        long long ans_K = (N_factorial * f[k]) % MOD;
        std::cout << ans_K << "\n";
    }

    return 0;
}
0