考察
ある値が初めて追加された時点では、その個数は必ず一個である。その後の期待個数は、他の値の内訳を追わずに、列の長さだけから求められる。そこで初登場の時刻で場合分けし、最後に時刻ごとの寄与を畳み込みでまとめる。
初登場した操作番号を固定する
操作番号を 、新しい値を追加する確率を とし、最終的な値 の個数の期待値を とする。毎回一要素を追加するため、操作 の直前の列長は 、直後は である。
新しい値は の順に現れる。したがって、 が操作 で初めて現れるには、最初の 回に新しい値の追加がちょうど 回あり、操作 でも新しい値を追加すればよい。それ以前にどの既存値を複製したかは、この条件に影響しない。
の初登場時刻を とすると、 に対して
となる。二項係数は、先行する新値追加の位置を選んでいる。新値追加は操作 も含めて 回、既存値の複製は 回である。最後まで が現れなければ、その個数の寄与は零である。
初登場後の期待倍率を求める
すでに が現れていて、現在の列長が 、その個数が だとする。次の操作で が一個増える確率は、既存値を複製する確率と、その中で を選ぶ確率の積 である。よって、その時点までの操作をすべて固定したとき、次の個数の条件付き期待値は
になる。倍率は列長だけで決まり、個数には線形に掛かる。
列長 のときの の個数を確率変数 とする。起こりうる初登場時刻 で条件付けたまま、それまでの操作についても平均を取ると、条件付き期待値の反復により
が成り立つ。個数と未来の操作の独立性を仮定する必要はない。実際、次に を選ぶ確率は現在の個数に依存している。
残り 回、すなわち現在の列長が の時点から最後までの期待倍率を と置く。初登場直後は一個なので、操作 で初登場した場合の最終期待個数は、残り 回に対応する である。
残り零回なら 。残り 回なら、まず列長 で一回操作し、続く 回の倍率を掛けるから
と前計算できる。 の初登場は最も早くても操作 なので、必要なのは だけである。
時刻の和を畳み込みの添字へ変える
初登場の確率と、その後の期待個数を掛け、互いに排反な初登場時刻について足すと
を得る。確率零の時刻の寄与は零とする。この式を各 について直接計算すると、項数の合計が となり、時間は かかる。 では、異なる の計算を共有したい。
そのために、初登場前に既存値を複製した回数を 、初登場後の残り操作回数を と置く。
が から まで動くと、 は から まで増え、 は から まで減る。両者の和は
で一定になる。また、 より なので
である。二項係数の分母にも を代入すると
となる。これを時刻和へ戻すと、外へ出せる だけの因子を除き、 だけの因子と だけの因子に分かれる。
ここで初めて、二つの係数列を
と定義する。多項式 、 の積では、次数 の係数がちょうど を満たす積を集める。したがって
である。 は次数 の係数を取り出す記号である。一回の畳み込みで、すべての の内側の和を計算できる。
三要素の例で時刻と係数を確かめる
とする。、 である。
値 が操作 で初登場する確率は で、残り一回の期待倍率は 。操作 で初登場する確率は、先に複製し、次に新値を追加する確率 で、残り操作はない。従って
となる。値 が現れるには二回とも新値追加でなければならず、 である。
係数列からも、、 となる。 では次数 を読み、。 では定数項を読み、 と一致する。
どの操作列でも最終的な全個数の和は なので、期待値の線形性から
で求められる。この例では で、公式問題のサンプルとも一致する。
法上で計算する手順
導出は通常の確率で行ったが、答えは法 上で求める。 とし、以降の除算を逆元の乗算へ置き換える。
- 階乗・逆階乗、必要な整数の逆元、 と の累乗を 時間で前計算する。
- から まで漸化式で求め、長さ の係数列 を作る。
- NTTで通常の畳み込み を一回計算する。
- について を求め、保存則から を求める。
典型の発動条件
初登場時刻による条件付け
種類が新たに生まれてから増える過程では、まず一種類の初登場時刻を固定する。その直後の個数が決まれば、「生まれる確率」と「生まれた後の期待個数」に分けて寄与を足せる。最後まで生まれない場合の寄与も確認する。
期待値の乗法漸化式
現在の状態を固定した一歩先の期待個数が、現在個数に既知の倍率を掛けた形なら、その式を平均して期待個数の漸化式を得られる。本問では倍率が列長だけで決まるため、個数分布を保持せずに済む。増加確率が個数に非線形に依存する場合は、同じ閉じた漸化式になるとは限らない。
生成関数と convolution
多数の答えが の形で表せ、答えによって変わるのが読む次数 だけなら、一回の畳み込みでまとめられる。二項係数が混ざる和では階乗へ展開し、外側の変数だけの因子と、二つの添字それぞれの因子へ分離できるか調べる。
問題固有の要素
新値は順番に現れるので、値 の初登場は、新値追加が通算 回目となる操作で決まる。一方、複製による期待倍率は他の種類の内訳によらず、列長だけで決まる。この二点が、初登場時刻だけを列挙する方針を支えている。
さらに、初登場前の複製回数と初登場後の残回数の和が になる。この「前後に残った回数の和」に注目すると、どの次数を読むかと、どの二列を畳み込むかを同時に導ける。
正当性
が初登場する操作 は一意であり、その事象は先行する新値追加が 回で操作 も新値追加となることと同値である。従って二項確率は各初登場時刻の確率を正しく数え、未登場の場合の個数は零である。初登場直後の個数は一個で、その後の一歩の条件付き期待個数は現在個数の 倍となる。この式を繰り返し平均することで、残り 回後の期待個数は と求まる。よって時刻和は に等しい。変数変換 は、時刻の範囲と を一対一に対応させる。階乗の展開で各項の重みも保たれるため、畳み込み係数から同じ時刻和が得られる。最後に全個数の和が常に であることから、残差で求めた も正しい。
実装上の注意
- の添字は「残り操作回数」であり、操作番号ではない。 の階乗添字は 、 が読む係数は と区別する。
- なら新しい値は現れず、、他は零。 なら となり、すべての である。上の式は両端も扱える。累乗の初期値は常に とし、 でもこの規約を使う。
- では だけが寄与し、 となる。 では両係数列が長さ一で、、 である。
- 階乗・逆階乗の必要範囲は 。倍率の分母 と も法で非零なので逆元が存在する。 や の逆元は使わない。
- 各係数列の長さは で、通常の積の長さは 。自前のNTTではこの長さ以上の二冪まで零埋めし、高次係数の折り返しを防ぐ。
復習の核
- 生まれてから増える過程では、初登場時刻を固定して「出現の確率」と「その後の期待倍率」を切り分ける。
- 一歩先の条件付き期待値が現在個数に線形なら、独立性を仮定せず、平均を取って期待値の漸化式を閉じられる。
- 時刻の和を畳み込みにするときは、まず新しい二つの添字とその和を書く。読む係数も階乗添字も、その対応から導く。
計算量と制約
時間
。階乗・逆元・累乗・期待倍率と係数列の準備は 、長さ 同士の畳み込みは 、全期待値の取り出し・保存則による集計と出力は である。
空間
。前計算の配列、係数列と積、NTTの作業領域、答えを保持する。
制約との対応
公式制約は 、、入力はすべて整数である。法 は必要な分母より大きい素数である。積の長さは最大 なので、NTTの変換長は最大 となり、この法で計算できる。
出典