ABC 281 Ex — Alchemy

考察

level iの宝石を作るには、材料をi個選ぶ。level1は在庫が十分でも、一回の合成ではA種類から異なる種類を選び、各種類を高々1個使う。したがって各種類の因子は1+z。level j≥2は種類によらず同じlevelを高々1個選ぶ。a_iをlevel iの生成方法数とすると、

a_i=[z^i](1+z)^A∏_{2≤j<i}(1+a_j z)

となる。各因子の次数は材料の個数、係数はその材料の生成方法数である。N=1ならAを返す。

a_iが決まるたびに長さNの係数列へ一次因子を掛けるとO(N²)。既知の一次因子なら積木でまとめられるが、本問は積の係数が次の因子を作るので、左の答えを確定してから右へ進む必要がある。

区間再帰solve(l,r,g)を次の不変条件で定義する。引数は長さr−lの局所配列で、

g[t]=[z^(l+t)](1+z)^A∏_{2≤j<l}(1+a_j z) (0≤t<r−l)

である。返り値はQ_{l,r}(z)=∏_{l≤j<r}(1+a_j z)。初回はsolve(2,N+1,g)で、g[t]=C(A,2+t)とする。C(A,k)はC(A,0)=1からC(A,k)=C(A,k−1)(A−k+1)/kでNまで求める。

葉r=l+1ではa_l=g[0]を確定し、[1,a_l]を返す。内部ではm=floor((l+r)/2)として、以下を行う。

  1. gの先頭m−l個を渡して左を解き、積Q=Q_{l,m}を得る。
  2. 局所配列の畳み込みh=g*Qを計算し、hの添字[m−l,r−l)を右への配列として渡す。
  3. 右の返り値Q_{m,r}とQを畳み込み、Q_{l,r}を返す。

手順2で求める元の次数は[m,r)。Qの次数は高々m−lなので、元の次数l未満の係数は掛けてもm未満にしか届かない。従ってgを[l,r)に切ってよい。右へ渡すのは更新後の係数そのものであり、左因子の寄与を加法的に一回送るだけのCDQではない。Qの積に含まれる複数因子の交差項も、通常の多項式積で全て入る。

各長さsの呼出しは長さO(s)の畳み込みを定数回行う。NTTでO(s log s)、同一階層のsの和はO(N)、階層数はO(log N)なので全体O(N log²N)。

N=2,A=1ではlevel1の同種2個を材料にできず、(1+z)^1のz²係数も0になる。無制限在庫と、一回の合成で同じ種類を重ねてよいかは区別する。

典型の発動条件

組合せ選択の生成関数

発動条件: 複数categoryから0/1個または任意個選び、総材料数別の重み和を求めるとき。

level1の各種類の0/1選択を(1+z)^A、高levelのレベルごとの0/1選択を1+a_j zで表す。

online CDQ convolution

発動条件: 列a_iが過去a_jからなる畳み込み/多項式係数で順次定まり、全prefixを高速化したいとき。

左半分を確定してその寄与をNTTで右半分へ一括反映する。

問題固有の要素

各level≥2から材料を高々1個という制約が、未知係数a_jを持つlinear factor(1+a_jz)を生み、online product問題になる。

別の問題へ持ち帰る視点: 自己生成される種類数が後続の0/1選択factorになる再帰では、動的生成関数をCDQで確定順に処理する。

正当性

材料の選択をlevel1の二項係数と既知levelの0/1因子で表すと、材料数iの係数がa_iになる。solve(l,r,g)の不変条件の下で、左再帰は左のaを確定しその全因子積Qを返す。Qの次数はm−l以下なので、右が必要とする次数[m,r)へ元の次数l未満は寄与しない。従って局所畳み込み(g*Q)[m−l:r−l]は右の不変条件を満たす。葉は全ての過去因子を反映した係数を読み、返り値は左右の積から正しい区間積になる。帰納的に素朴な母関数更新と一致する。

実装上の注意

  • Aは法998244353を超え得るが、k≤N<法なのでkの逆元が存在し、二項係数の漸化式を法上で使える。
  • gの添字は元の次数からlを引いたもの。返す因子積の添字は通常の次数であり、両者を混同しない。
  • 各畳み込み後は次の呼出しに必要な区間を切り出す。全次数配列を各葉へ持ち込まない。

復習の核

  • N=2でa_2=C(A,2)、N=3でC(A,3)+C(A,2)a_2をfactor展開から導き、CDQが確定済みa_2だけを右へ使うことを確認する。

計算量と制約

時間

二項係数の前計算O(N)。長さsの再帰でO(s log s)のNTTを定数回行い、階層ごとの総和O(N log N)をO(log N)階層分足すので、全体O(N log²N)。

空間

O(N log N)の再帰保持、解放を工夫すればO(N)。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq A \leq 10^9; N and A are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Alchemy の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 組合せを生成関数へ符号化する

主題
追加で学ぶ技能
  • Relaxed・online convolution: 係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
既習技能

主タグ: 生成関数による組合せ構造の符号化 Relaxed・online convolution

補助タグ: 畳み込み・相互相関 再帰分割・分割統治

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

学習の位置

体系上の位置: 組合せを生成関数へ符号化する

  • 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。
  • 係数が順に確定する因果的畳み込みをblock分割し、確定済みblock間だけをNTTでまとめて更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

先に読む単元:

この解説で扱わないこと:

  • 係数列同士を単に畳み込む相互相関、および係数の組合せ的意味を持たない信号処理。

学習記録

状況更新: 更新記録なし

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

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

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

同じ単元の問題