Ex - add 1 Editorial by maspy

別解っぽいので書きます。

方針

形式的べき級数 \(F, G, H\) を次のように定めます。

  • ちょうど \(n\) 回ではじめて終了状態に到達する確率を\(F_n\)とし、\(F(x) = \sum_{n} F_nx^n\) とする。
  • 終了状態に到達しても無視して操作を行い続けることにする。\(G_n\) を、\(n\) 回操作したときに終了状態にいる確率とする。\(G(x) = \sum_{n} G_nx^n\) とする。
  • 終了状態から 操作を始めることにする。\(H_n\) を \(n\) 回操作したときに終了状態にいる確率とする。\(H(x) = \sum_nH_nx^n\) とする。

\(G_n\) を、はじめて終了状態に到達した時刻ごとに計算して合計することを考えると、\(G_n = \sum_{i+j=n}F_iH_j\) が分かります。よって \(F(x)H(x)=G(x)\)、\(F(x)=\frac{G(x)}{H(x)}\) が分かります。

求めるべきは、\(\sum_{n=0}^{\infty} nF_n = F'(1)\) です。 \(G(x)\), \(H(x)\) は後述のように有理式になるため，\(F\) も有理式で、それを有理式として微分して \(1\) を代入すればよいです。（有理式への代入と係数和の一致の正当化は https://atcoder.jp/contests/arc136/editorial/3461 を参照してください）

\(G\) の計算

\(A_i\) を \(0\) にする操作を 「操作 \(i\)」 と呼ぶことにします。 \(n\) 回操作後に終了状態に到達していることは、次と同値です。

  • \(n \geq \max(A)\)
  • 末尾から \(A_i\) 回以内では、\(i\) は削除対象ではない

例えば \(A = [0, 2,5,10]\) であれば、

  • 末尾から \(0, 1\) 回目は操作 \(1\)
  • 末尾から \(2,3,4\) 回目は操作 \(1, 2\)
  • 末尾から \(5,6,7,8,9\) 回目は操作 \(1, 2, 3\)
  • 末尾から \(10\) 回目以降は操作 \(1, 2, 3, 4\)

という具合で、\(G_n = (1/4)^2\cdot (2/4)^3\cdot (3/4)^5\cdot (4/4)^{n-10}\) などとなります。

\(\max(A)=d\) として、\(G(x) = cx^d(1+x+x^2+\cdots) = \frac{cx^d}{1-x}\) の形です。

\(H\) の計算

終了状態から始めたとき、\(n\) 回操作後に終了状態に到達していることは、次と同値です。

  • 末尾から \(A_i\) 回以内では、\(i\) は削除対象ではない

これは、「\(G\) の計算」において「\(n\geq \max(A)\)」の条件がなくなっただけです。

回数の区間ごとに等比数列の係数が並んで、 \(H(x) = d \text{次未満多項式} + \frac{cx^d}{1-x}\)

の形です。この多項式の部分は、区間ごとに \(x^l(1+px+\cdots+(px)^{r-l-1})\) の定数倍を足す形で、これも計算が簡単です。

答の計算

多項式 \(P, Q\) を用いて \(G(x) = \frac{P(x)}{1-x}\), \(H(x) = \frac{Q(x)}{1-x}\) と書けることが分かりました。また、\(H(x) = \text{多項式} + \frac{cx^d}{1-x}\) の形で、\(c\neq 0\) であることもすぐに分かるので、\(Q(1)\neq 0\) が成り立ちます。

よって \(F(x) = \frac{G(x)}{H(x)} = \frac{P(x)}{Q(x)}\) は \(Q(1)\neq 0\) であるような有理式で、\(F'(1) = \frac{P'(1)Q(1)-P(1)Q'(1)}{Q(1)^2}\) により答が計算できます。

解答例

解説と記号をそろえるなどの調整は行っていません。

posted:
last update: