Day 156-Q2 — 五角数定理による分割数（Euler's Pentagonal Number Theorem）

2026-09-17 赤色 Master / Phase 8+ ★★★★★★★★★ $p(n)$ を $O(N\sqrt N)$ の疎な漸化式で

問題

正整数 $n$ の分割数 $p(n)$ とは、$n$ を正整数の和として表す方法の数（順序は区別しない）。例えば $p(4)=5$：$4,\ 3+1,\ 2+2,\ 2+1+1,\ 1+1+1+1$。

整数 $N$ が与えられるので、$p(0),\dots,p(N)$ を $998244353$ で割った余りをすべて出力せよ（$p(0)=1$）。

入力形式

N

制約

変数範囲補足
$N$$1\le N\le 5\times10^4$$O(N^2)$ DP は $2.5\times10^9$ 回で不可
法$998244353$NTT 素数（本問では NTT は使わない）

入出力例

入力例1

10

出力例1

1 1 2 3 5 7 11 15 22 30 42

入力例2

100

出力例2（$p(100)$ のみ抜粋）

... 190569292

概念図：$p(10)$ は一般化五角数だけ手前の $p$ から決まる

p(10) = +p(9) +p(8) −p(5) −p(3) = 30+22−7−3 = 42 01234 5678910 p=11235 71115223042 −1 (+) −2 (+) −5 (−) −7 (−) 一般化五角数 g = 1,2,5,7,12,15,22,26,… （k=±1,±2,…に対する k(3k−1)/2）。符号は 2 個ずつ + + − − + + − − … n=10 では 12 以降が届かないので 4 項で終わる → 各 n について O(√n) 項

ヒント（段階的開示）

ヒント1（方向性）

「$k$ 以下の部分だけで $n$ を作る」2次元 DP（$O(N^2)$）はすぐ書ける。まずそれで $p(0..10)$ を確認し、$N=5\times10^4$ で $2.5\times10^9$ 回の更新が必要になることを見積もってから次に進む。

ヒント2（アプローチ）

母関数 $P(x)=\prod_{k\ge1}\frac1{1-x^k}$ の逆数 $\prod(1-x^k)$ は Euler の五角数定理によりほとんどの係数が 0：$$\prod_{k\ge1}(1-x^k)=\sum_{k=-\infty}^{\infty}(-1)^kx^{k(3k-1)/2}=1-x-x^2+x^5+x^7-x^{12}-x^{15}+\cdots$$ $P(x)\cdot\prod(1-x^k)=1$ の係数比較で、$p(n)$ は一般化五角数だけ前の $p$ の符号つき和になる。

ヒント3（誘導）
$$p(n)=\sum_{k\ge1}(-1)^{k+1}\Big(p\big(n-\tfrac{k(3k-1)}2\big)+p\big(n-\tfrac{k(3k+1)}2\big)\Big)$$ 
for n in range(1, N + 1):
    k = 1; s = 0
    while k*(3*k-1)//2 <= n:
        sign = 1 if k % 2 == 1 else -1
        s += sign * p[n - k*(3*k-1)//2]
        if k*(3*k+1)//2 <= n:
            s += sign * p[n - k*(3*k+1)//2]
        k += 1
    p[n] = s % MOD

模範解答 (Python)

import sys

MOD = 998244353

def partitions(N: int) -> list[int]:
    p = [0] * (N + 1)
    p[0] = 1
    for n in range(1, N + 1):
        k = 1
        s = 0
        while True:
            g1 = k * (3 * k - 1) // 2        # 一般化五角数 (k > 0 側)
            if g1 > n:
                break
            sign = 1 if k & 1 else -1        # 符号は (-1)^{k+1}
            s += sign * p[n - g1]
            g2 = k * (3 * k + 1) // 2        # 一般化五角数 (k < 0 側)
            if g2 <= n:
                s += sign * p[n - g2]
            k += 1
        p[n] = s % MOD                       # Python の % は常に非負
    return p

def main():
    N = int(sys.stdin.readline())
    print(*partitions(N))

main()

Step-by-Step 解説

1五角数定理が「疎な逆数」を与える
$\prod(1-x^k)$ の非零係数は一般化五角数 $1,2,5,7,12,15,22,26,35,40,\dots$ の位置にしか現れない（$k=1..5$ で列挙し実測確認）。符号は $k$ ごとに $-,-,+,+,\dots$ と 2 個ずつ入れ替わる。「疎な多項式で割る」＝各 $n$ で $O(\sqrt n)$ 項の漸化式。
2実測（本ページ作成時に Python で実行）
方法$N=10$$N=100$$N=20000$ 所要時間内部ループ加算回数
五角数漸化式 $O(N\sqrt N)$1 1 2 3 5 7 11 15 22 30 421905692920.505 s3,059,460
2次元 DP $O(N^2)$完全一致190569292（一致）15.331 s約 $2\times10^8$
$p(100)=190569292$ は OEIS A000041 と一致。$N=5\times10^4$ では五角数版が推定約 2 s（$N^{1.5}$ スケールからの導出値・未実測）、$O(N^2)$ 版は推定 95 s（導出値）。

迷った他案と採らなかった理由

案計算量採否理由
2次元 DP$O(N^2)$検算用のみ$N=5\times10^4$ で不可
五角数漸化式$O(N\sqrt N)$採用40 行以内・整数演算のみ。$N\le10^5$ 程度まで Python で現実的
FPS 逆元（NTT）$O(N\log N)$不採用$N\ge2\times10^5$ では必須だが、Day 055 の Newton 法実装が前提になり主題から離れる。制約が $N\le10^6$ なら NTT 版一択
$\exp(\sum\log)$ ルート$O(N\log N)$不採用$\log(1-x^k)$ の調和和で落ちる別ルートだが、係数の疎性という核心を通らない

よくあるミス

ミス原因正しい書き方
$k<0$ 側の五角数 $k(3k+1)/2$ を忘れる一般化五角数は $k=\pm1,\pm2,\dots$ の両側g1 と g2 の両方を同じ符号で加える
符号を $(-1)^k$ にする$\prod(1-x^k)$ 側と移項後の $p(n)$ 側の取り違えsign = 1 if k % 2 == 1 else -1
他言語移植時に負の剰余が残るC++ の % は負を返す((s % MOD) + MOD) % MOD
p[0]=0 で初期化空の分割を 1 通りと数える約束p[0] = 1

次のステップ

  • 関連する実問題: Project Euler 78「Coin partitions」（五角数漸化式が想定解）
  • 発展: 「相異なる部分への分割」と「奇数部分だけの分割」の個数が等しい Euler の定理を母関数から示し、同じ型で計算する
  • 扱わなかった範囲: $N\ge2\times10^5$ で必要な NTT による FPS 逆元版（Day 055）
  • 次回予告: ヨセフス問題（$O(N)$ と $O(K\log N)$）

自己評価

自分の回答

気づき・メモ