test/yosupo/enumerative_conbinatorics/partition_function.test.cpp

AC · 最終更新 2026-09-07 · GitHub

問題: https://judge.yosupo.jp/problem/partition_function

依存するヘッダ（12）

二項係数・階乗・順列・多項係数・重複組合せ lib/combinatorics/combinatorics.hpp
分割数を $p(0)$ から $p(n)$ まで列挙する lib/combinatorics/partition_function.hpp
形式的冪級数 (FPS) lib/convolution/formal_power_series.hpp
NTT・畳み込み (convolution) lib/convolution/ntt.hpp
Montgomery + AVX2 による NTT 畳み込み (NTT-friendly な 32bit 素数 mod 専用) lib/convolution/ntt_avx2.hpp
internal/internal_fft.hpp lib/internal/internal_fft.hpp
internal/internal_fft_avx2.hpp lib/internal/internal_fft_avx2.hpp
internal/internal_fps_avx2.hpp lib/internal/internal_fps_avx2.hpp
internal/internal_math.hpp lib/internal/internal_math.hpp
internal/internal_type_traits.hpp lib/internal/internal_type_traits.hpp
modint (static_modint / dynamic_modint) lib/number_theory/modint.hpp
素数法上で `x` の平方根を 1 つ返す lib/number_theory/root_mod.hpp

実装

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/partition_function
#include <iostream>
#include "combinatorics/partition_function.hpp"

using Mint = modint998;

int main(void) {
    int n;
    std::cin >> n;
    auto ans = partition_function<Mint>(n);
    for (int i = 0; i <= n; ++i) std::cout << ans[i] << " \n"[i == n];

    return 0;
}