ABC 279 Ex — Sum of Prod of Min

考察

各S_kの寄与min(k,S_k)を係数とする生成関数を掛ければ、ΣS_k=Mの重み総和は積のx^M係数になる。

d=M-N≤Nなので、各要素から最低1を引いた後に必要な次数はN以下に限られ、有限積∏_{i=1}^N(1-x^i)を無限積へ置き換えても低次係数は変わらない。

採用する候補: 各factorをx(1-x^k)/(1-x)^2へ変形し、Eulerの五角数定理で分子の疎な係数だけ列挙し、分母係数をLucas定理の二項係数で足す。

Nが10^12でも必要な分子項は√N個で、巨大引数の組合せを小さい法200003のdigitごとに計算できる。

棄却する候補: kと現在sumを持つknapsack DPで生成関数の係数を順に更新する。

N,Mが10^12で状態もfactor数も列挙できない。

Σ_{s≥1}min(k,s)x^sは係数差分を2回取るとx-x^{k+1}となり、x(1-x^k)/(1-x)^2を得る。

Euler積の非零次数はgeneralized pentagonal numbers t(3t±1)/2、係数は(-1)^tなのでd以下に疎にしか現れない。

[x^{d-e}](1-x)^{-2N}=C(M+N-e-1,2N-1)であり、prime modulusのLucas定理で巨大Nのまま求められる。

d=M-Nとし、e=0およびt(3t±1)/2≤dを列挙する。符号(-1)^tを掛けたC(M+N-e-1,2N-1)をmod200003で加算する。二項係数は0…p-1のfactorial/逆factorialを前計算してLucasで評価する。

典型の発動条件

重み付き列の生成関数

発動条件: 独立な各位置の値と重みの積を、総和条件の下で合計するとき。

位置kのΣ weight(s)x^sを作り、全factor積の指定係数を取る。

Euler pentagonal number theorem

発動条件: partition関連の∏(1-x^i)が現れ、低次係数だけ必要なとき。

無限積をgeneralized pentagonal number上の疎な±1級数へ展開する。

Lucas theorem

発動条件: prime pを法とする二項係数の上下引数が非常に大きいとき。

base-p digitごとの小二項係数の積として計算する。

問題固有の要素

M≤2Nにより必要次数d≤Nとなるため、有限Euler積のtailを捨てて有名な無限積公式をそのまま使える。

別の問題へ持ち帰る視点: 有限積を無限積へ延長する際は、求める係数次数より追加factorの最小次数が大きいかを確認する。

正当性

各因子Σ_{s≥1}min(k,s)x^s=x(1−x^k)/(1−x)²なので全積はx^NΠ_{k≤N}(1−x^k)/(1−x)^{2N}。d=M−N≤Nの範囲ではk>Nの因子は低次を変えず無限Euler積へ替えられる。五角数定理で非零項だけを出し、残りの係数を巨大二項係数としてLucasで正確に評価すれば目的の重み和を得る。

実装上の注意

  • generalized pentagonal numberはtの±側t(3t-1)/2,t(3t+1)/2を重複なく列挙し、e=0の符号は+1とする。
  • 通常のmod998244353ではなくp=200003でfactorialと全演算を行い、巨大な二項引数には64 bitを使う。

復習の核

  • k=3の係数列1,2,3,3,…へ(1-x)を2回掛けてx-x^4になることと、d≤Nが無限積化を許す理由を確認する。

計算量と制約

時間

O(p+√(M−N) log_p(N+M))、p=200003。五角数だけ列挙してLucasを適用する。

空間

O(p)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{12}; N \leq M \leq 2N; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sum of Prod of Min の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 母関数方程式・高度な係数抽出

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 母関数方程式・高度な係数抽出

    補助タグ: 組合せ係数・数え上げ

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 母関数方程式・高度な係数抽出

    • Eulerの五角数定理により∏(1−x^i)を符号付きの疎な係数列へ展開し、必要次数までのO(√N)項で係数抽出できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題