ABC 409 G — Accumulation of Wealth

考察

ある値が初めて追加された時点では、その個数は必ず一個である。その後の期待個数は、他の値の内訳を追わずに、列の長さだけから求められる。そこで初登場の時刻で場合分けし、最後に時刻ごとの寄与を畳み込みでまとめる。

初登場した操作番号を固定する

操作番号を t=1,…,N−1t=1,\ldots,N-1、新しい値を追加する確率を p=P/100p=P/100 とし、最終的な値 kk の個数の期待値を EkE_k とする。毎回一要素を追加するため、操作 tt の直前の列長は tt、直後は t+1t+1 である。

新しい値は 2,3,…2,3,\ldots の順に現れる。したがって、k≥2k\geq 2 が操作 tt で初めて現れるには、最初の t−1t-1 回に新しい値の追加がちょうど k−2k-2 回あり、操作 tt でも新しい値を追加すればよい。それ以前にどの既存値を複製したかは、この条件に影響しない。

kk の初登場時刻を TkT_k とすると、k−1≤t≤N−1k-1\leq t\leq N-1 に対して

Pr⁡(Tk=t)=(t−1k−2)pk−1(1−p)t−k+1\Pr(T_k=t)=\binom{t-1}{k-2}p^{k-1}(1-p)^{t-k+1}

となる。二項係数は、先行する新値追加の位置を選んでいる。新値追加は操作 tt も含めて k−1k-1 回、既存値の複製は t−k+1t-k+1 回である。最後まで kk が現れなければ、その個数の寄与は零である。

初登場後の期待倍率を求める

すでに kk が現れていて、現在の列長が nn、その個数が cc だとする。次の操作で kk が一個増える確率は、既存値を複製する確率と、その中で kk を選ぶ確率の積 (1−p)c/n(1-p)c/n である。よって、その時点までの操作をすべて固定したとき、次の個数の条件付き期待値は

c+(1−p)cn=n+1−pncc+(1-p)\frac{c}{n}=\frac{n+1-p}{n}c

になる。倍率は列長だけで決まり、個数には線形に掛かる。

列長 nn のときの kk の個数を確率変数 CnC_n とする。起こりうる初登場時刻 Tk=tT_k=t で条件付けたまま、それまでの操作についても平均を取ると、条件付き期待値の反復により

E[Cn+1∣Tk=t]=n+1−pnE[Cn∣Tk=t](n≥t+1)\mathbb{E}[C_{n+1}\mid T_k=t] =\frac{n+1-p}{n}\mathbb{E}[C_n\mid T_k=t] \qquad(n\geq t+1)

が成り立つ。個数と未来の操作の独立性を仮定する必要はない。実際、次に kk を選ぶ確率は現在の個数に依存している。

残り jj 回、すなわち現在の列長が N−jN-j の時点から最後までの期待倍率を f(j)f(j) と置く。初登場直後は一個なので、操作 tt で初登場した場合の最終期待個数は、残り N−t−1N-t-1 回に対応する f(N−t−1)f(N-t-1) である。

残り零回なら f(0)=1f(0)=1。残り jj 回なら、まず列長 N−jN-j で一回操作し、続く j−1j-1 回の倍率を掛けるから

f(j)=N−j+1−pN−jf(j−1)(1≤j≤N−2)f(j)=\frac{N-j+1-p}{N-j}f(j-1) \qquad(1\leq j\leq N-2)

と前計算できる。k≥2k\geq 2 の初登場は最も早くても操作 11 なので、必要なのは f(0),…,f(N−2)f(0),\ldots,f(N-2) だけである。

時刻の和を畳み込みの添字へ変える

初登場の確率と、その後の期待個数を掛け、互いに排反な初登場時刻について足すと

Ek=∑t=k−1N−1(t−1k−2)pk−1(1−p)t−k+1f(N−t−1)(2≤k≤N)E_k=\sum_{t=k-1}^{N-1} \binom{t-1}{k-2}p^{k-1}(1-p)^{t-k+1}f(N-t-1) \qquad(2\leq k\leq N)

を得る。確率零の時刻の寄与は零とする。この式を各 kk について直接計算すると、項数の合計が 1+2+⋯+(N−1)1+2+\cdots+(N-1) となり、時間は O(N2)O(N^2) かかる。N≤105N\leq 10^5 では、異なる kk の計算を共有したい。

そのために、初登場前に既存値を複製した回数を ss、初登場後の残り操作回数を jj と置く。

s=t−k+1,j=N−t−1s=t-k+1,\qquad j=N-t-1

tt が k−1k-1 から N−1N-1 まで動くと、ss は 00 から N−kN-k まで増え、jj は N−kN-k から 00 まで減る。両者の和は

s+j=(t−k+1)+(N−t−1)=N−ks+j=(t-k+1)+(N-t-1)=N-k

で一定になる。また、j=N−t−1j=N-t-1 より t=N−j−1t=N-j-1 なので

(t−1)!=(N−j−2)!(t-1)!=(N-j-2)!

である。二項係数の分母にも t−k+1=st-k+1=s を代入すると

(t−1k−2)=(t−1)!(k−2)!(t−k+1)!=(N−j−2)!(k−2)!s!\binom{t-1}{k-2} =\frac{(t-1)!}{(k-2)!(t-k+1)!} =\frac{(N-j-2)!}{(k-2)!s!}

となる。これを時刻和へ戻すと、外へ出せる kk だけの因子を除き、jj だけの因子と ss だけの因子に分かれる。

Ek=pk−1(k−2)!∑j,s≥0j+s=N−kf(j)(N−j−2)!⏟j だけの因子(1−p)ss!⏟s だけの因子E_k=\frac{p^{k-1}}{(k-2)!} \sum_{\substack{j,s\geq 0\\j+s=N-k}} \underbrace{f(j)(N-j-2)!}_{j\text{ だけの因子}} \underbrace{\frac{(1-p)^s}{s!}}_{s\text{ だけの因子}}

ここで初めて、二つの係数列を

Fj=f(j)(N−j−2)!,Gs=(1−p)ss!(0≤j,s≤N−2)F_j=f(j)(N-j-2)!,\qquad G_s=\frac{(1-p)^s}{s!} \qquad(0\leq j,s\leq N-2)

と定義する。多項式 F(x)=∑j=0N−2FjxjF(x)=\sum_{j=0}^{N-2}F_jx^j、G(x)=∑s=0N−2GsxsG(x)=\sum_{s=0}^{N-2}G_sx^s の積では、次数 N−kN-k の係数がちょうど j+s=N−kj+s=N-k を満たす積を集める。したがって

Ek=pk−1(k−2)![xN−k](F(x)G(x))(2≤k≤N)E_k=\frac{p^{k-1}}{(k-2)!}[x^{N-k}](F(x)G(x)) \qquad(2\leq k\leq N)

である。[xd][x^d] は次数 dd の係数を取り出す記号である。一回の畳み込みで、すべての kk の内側の和を計算できる。

三要素の例で時刻と係数を確かめる

N=3,p=1/2N=3,p=1/2 とする。f(0)=1f(0)=1、f(1)=(3−1/2)/2=5/4f(1)=(3-1/2)/2=5/4 である。

値 22 が操作 11 で初登場する確率は 1/21/2 で、残り一回の期待倍率は 5/45/4。操作 22 で初登場する確率は、先に複製し、次に新値を追加する確率 (1/2)(1/2)(1/2)(1/2) で、残り操作はない。従って

E2=12⋅54+12⋅12⋅1=78E_2=\frac12\cdot\frac54+\frac12\cdot\frac12\cdot 1=\frac78

となる。値 33 が現れるには二回とも新値追加でなければならず、E3=(1/2)2=1/4E_3=(1/2)^2=1/4 である。

係数列からも、F(x)=1+(5/4)xF(x)=1+(5/4)x、G(x)=1+(1/2)xG(x)=1+(1/2)x となる。k=2k=2 では次数 N−k=1N-k=1 を読み、E2=(1/2)(5/4+1/2)=7/8E_2=(1/2)(5/4+1/2)=7/8。k=3k=3 では定数項を読み、E3=(1/2)2⋅1=1/4E_3=(1/2)^2\cdot 1=1/4 と一致する。

どの操作列でも最終的な全個数の和は NN なので、期待値の線形性から

E1=N−∑k=2NEkE_1=N-\sum_{k=2}^N E_k

で求められる。この例では E1=3−7/8−1/4=15/8E_1=3-7/8-1/4=15/8 で、公式問題のサンプルとも一致する。

法上で計算する手順

導出は通常の確率で行ったが、答えは法 998244353998244353 上で求める。p=P⋅100−1p=P\cdot 100^{-1} とし、以降の除算を逆元の乗算へ置き換える。

  1. 階乗・逆階乗、必要な整数の逆元、pp と 1−p1-p の累乗を O(N)O(N) 時間で前計算する。
  2. f(0)=1f(0)=1 から f(N−2)f(N-2) まで漸化式で求め、長さ N−1N-1 の係数列 F,GF,G を作る。
  3. NTTで通常の畳み込み H=F∗GH=F*G を一回計算する。
  4. k=2,…,Nk=2,\ldots,N について Ek=pk−1HN−k/(k−2)!E_k=p^{k-1}H_{N-k}/(k-2)! を求め、保存則から E1E_1 を求める。

典型の発動条件

初登場時刻による条件付け

種類が新たに生まれてから増える過程では、まず一種類の初登場時刻を固定する。その直後の個数が決まれば、「生まれる確率」と「生まれた後の期待個数」に分けて寄与を足せる。最後まで生まれない場合の寄与も確認する。

期待値の乗法漸化式

現在の状態を固定した一歩先の期待個数が、現在個数に既知の倍率を掛けた形なら、その式を平均して期待個数の漸化式を得られる。本問では倍率が列長だけで決まるため、個数分布を保持せずに済む。増加確率が個数に非線形に依存する場合は、同じ閉じた漸化式になるとは限らない。

生成関数と convolution

多数の答えが ∑j+s=dajbs\sum_{j+s=d}a_jb_s の形で表せ、答えによって変わるのが読む次数 dd だけなら、一回の畳み込みでまとめられる。二項係数が混ざる和では階乗へ展開し、外側の変数だけの因子と、二つの添字それぞれの因子へ分離できるか調べる。

問題固有の要素

新値は順番に現れるので、値 kk の初登場は、新値追加が通算 k−1k-1 回目となる操作で決まる。一方、複製による期待倍率は他の種類の内訳によらず、列長だけで決まる。この二点が、初登場時刻だけを列挙する方針を支えている。

さらに、初登場前の複製回数と初登場後の残回数の和が N−kN-k になる。この「前後に残った回数の和」に注目すると、どの次数を読むかと、どの二列を畳み込むかを同時に導ける。

正当性

k≥2k\geq 2 が初登場する操作 tt は一意であり、その事象は先行する新値追加が k−2k-2 回で操作 tt も新値追加となることと同値である。従って二項確率は各初登場時刻の確率を正しく数え、未登場の場合の個数は零である。初登場直後の個数は一個で、その後の一歩の条件付き期待個数は現在個数の (n+1−p)/n(n+1-p)/n 倍となる。この式を繰り返し平均することで、残り N−t−1N-t-1 回後の期待個数は f(N−t−1)f(N-t-1) と求まる。よって時刻和は EkE_k に等しい。変数変換 s=t−k+1,j=N−t−1s=t-k+1,j=N-t-1 は、時刻の範囲と j,s≥0,j+s=N−kj,s\geq 0,j+s=N-k を一対一に対応させる。階乗の展開で各項の重みも保たれるため、畳み込み係数から同じ時刻和が得られる。最後に全個数の和が常に NN であることから、残差で求めた E1E_1 も正しい。

実装上の注意

  • ff の添字は「残り操作回数」であり、操作番号ではない。FjF_j の階乗添字は N−j−2N-j-2、EkE_k が読む係数は N−kN-k と区別する。
  • p=0p=0 なら新しい値は現れず、E1=NE_1=N、他は零。p=1p=1 なら f(j)=1f(j)=1 となり、すべての Ek=1E_k=1 である。上の式は両端も扱える。累乗の初期値は常に a0=1a^0=1 とし、a=0a=0 でもこの規約を使う。
  • k=Nk=N では j=s=0j=s=0 だけが寄与し、EN=pN−1E_N=p^{N-1} となる。N=2N=2 では両係数列が長さ一で、E2=pE_2=p、E1=2−pE_1=2-p である。
  • 階乗・逆階乗の必要範囲は 0,…,N−20,\ldots,N-2。倍率の分母 N−jN-j と 100100 も法で非零なので逆元が存在する。pp や 1−p1-p の逆元は使わない。
  • 各係数列の長さは N−1N-1 で、通常の積の長さは 2N−32N-3。自前のNTTではこの長さ以上の二冪まで零埋めし、高次係数の折り返しを防ぐ。

復習の核

  • 生まれてから増える過程では、初登場時刻を固定して「出現の確率」と「その後の期待倍率」を切り分ける。
  • 一歩先の条件付き期待値が現在個数に線形なら、独立性を仮定せず、平均を取って期待値の漸化式を閉じられる。
  • 時刻の和を畳み込みにするときは、まず新しい二つの添字とその和を書く。読む係数も階乗添字も、その対応から導く。

計算量と制約

時間

O(Nlog⁡N)O(N\log N)。階乗・逆元・累乗・期待倍率と係数列の準備は O(N)O(N)、長さ N−1N-1 同士の畳み込みは O(Nlog⁡N)O(N\log N)、全期待値の取り出し・保存則による集計と出力は O(N)O(N) である。

空間

O(N)O(N)。前計算の配列、係数列と積、NTTの作業領域、答えを保持する。

制約との対応

公式制約は 2≤N≤1052\leq N\leq 10^5、0≤P≤1000\leq P\leq 100、入力はすべて整数である。法 998244353=119⋅223+1998244353=119\cdot 2^{23}+1 は必要な分母より大きい素数である。積の長さは最大 199997199997 なので、NTTの変換長は最大 2182^{18} となり、この法で計算できる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Accumulation of Wealth の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: NTT・FFTで畳み込みと相互相関を求める

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

主タグ: 畳み込み・相互相関 生成関数による組合せ構造の符号化

補助タグ: 組合せ係数・数え上げ 法上の四則演算・高速累乗・逆元 確率・期待値DP

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

学習の位置

体系上の位置: NTT・FFTで畳み込みと相互相関を求める

  • 係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。
  • 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。

先に読む単元:

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

  • 組合せ解釈を必要とする生成関数の設計、および逆数・対数・指数などのFPS演算。

学習記録

状況更新: 更新記録なし

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

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

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

同じ単元の問題