# ARC180F Yet Another Expected Value 別解?

## 問題

https://atcoder.jp/contests/arc180/tasks/arc180_f

想定解はたぶん $N=10^5$ でも解けるのに対し別解はこの制約じゃないと無理です。計算量の意味では劣った解法になってしまいますが、他の例に応用がききそうな解法だと思うのでメモします。

## 別解の解説

### [1] 数え上げへの言いかえ

$x_1,x_2,\dots,x_n$ についての積の期待値を数え上げに言い換えます。具体例として以下の問題を考えてみます

<blockquote>

$0$ 以上 $1$ 以下の実数を一様ランダムに $5$ 個生成し、生成した実数を小さいほうから $x_1,x_2,\dots,x_5$ とする。 $x_2^2x_3$ の期待値を求めよ。

</blockquote>

ここで、固定された値 $x_2,x_3$ に対して $x_2^2x_3$ という値は以下の問題の答えに等しいです。

<blockquote>

$0$ 以上 $1$ 以下の実数を一様ランダムに $2+1$ 個生成し、それぞれ $y_1,y_2,y_3$ とする。 $y_1 < x_2, y_2 < x_2, y_3 < x_3$ となる確率を求めよ。

</blockquote>

よってこれら $2$ つを合わせると問題は以下のように言い換えられます。

<blockquote>

$0$ 以上 $1$ 以下の実数を一様ランダムに $5$ 個生成し、生成した実数を小さいほうから $x_1,x_2,\dots,x_5$ とする。その後、さらに $3$ 個生成し、生成した順に $y_1,y_2,y_3$ とする。 $y_1 < x_2, y_2 < x_2, y_3 < x_3$ を満たす確率を求めよ。

</blockquote>

これで生成した乱数の大小関係に関する確率の問題に言い換えられました。大小関係だけが気になる場合、乱数の生成は順列の生成に言い換えられて、最終的に以下のような数え上げの問題になります。

<blockquote>

黒いボールが $5$ 個と $1$ から $3$ までの番号が書かれてた白いボールがある。黒いボールについては互いに区別できない。これら $8$ 個のボールを横一列に並べるとき、以下の条件をすべて満たす並べ方の数を求めよ。

- 左から $2$ 番目の黒いボールの左側に白いボール $1$ が存在する
- 左から $2$ 番目の黒いボールの左側に白いボール $2$ が存在する
- 左から $3$ 番目の黒いボールの左側に白いボール $3$ が存在する

</blockquote>

これの答えは白いボール $1,2$ の挿入で $2 \times (2+1) = 6$ 通り、 白いボール $3$ の挿入で $(2+3) = 5$ 通りで $5 \times 6 = 30$ 個と求まります。すべての並べ方の数は $8 \times 7 \times 6$ 通り存在するので、期待値は $\frac{5}{56}$ と求まります。

### [2] $O(N^3+N^2\log{\mathrm{mod}})$ 解法

[1] の内容を踏まえて元の問題を解きます。

$\prod_{i=1}^{N}x_i^{k_i}$ の期待値の寄与を考える際は $\prod_{i=1}^{N}(1+\sum_{i<j}x_j)$ における係数も考える必要がありますが、これは $i=2,3,\dots,N$ の順に選べば $\prod_{i=2}^{N} \binom{i-1-\sum_{j i}k_j}{k_i}$ と求まります。これと期待値を合わせて考えると、答えへの寄与は

$$\displaystyle \frac{N!}{(N+A\sum k_i)!}\prod_{i=2}^{N}\binom{i-1-\sum_{j<i}k_j}{k_i} \frac{(i-1+Ak_i + A\sum_{j<i}k_j)!}{(i-1+A\sum_{j <i}k_j)!}$$

と求まります。

これらの総和については単純なDPで求まります。このDPでの計算を整理すると多項式 $f=1$ からはじめて、以下の処理を $i=1,2,\dots,N-1$ の順に行えばいいことが分かります。

1. $j=0,1,\dots,i$ に対し $[x^j]f$ を $\frac{(i-j)!}{(i+Aj)!}[x^j]f$ で置き換える
2. $f$ を $f \times e^x \bmod x^{(i+1)}$ で置き換える
3. $j=0,1,\dots,i$ に対し $[x^j]f$ を $\frac{(i+Aj)!}{(i-j)!}[x^j]f$ で置き換える

ここで、 $i$ での $3$ 番目の処理と $i+1$ での $1$ 番目の処理を合わせて考えると以下のような処理になります（一連の処理の後に $i=N-1$ での $3$ 番目の処理にあたることをする必要があります）。

1. $[x^j]f$ を $\frac{i-j}{i+Aj}[x^j]f$ で置き換える
2. $f$ を $f \times e^x \bmod x^{(i+1)}$ で置き換える

これは2番目の処理がボトルネックとなり $O(N^3+N^2\log{\mathrm{mod}})$ 時間での計算となります。

### [3] $e^x$ を軸にした高速化

$i$ での処理後の $f$ を $f_i$ とします。 $f_0=1$ であり、 $f_i$ は $i$ 次以下の多項式となります。

ボトルネックとなっている2番目の処理に合わせて、 $f_i$ の代わりに$f_i \equiv g_ie^{kx}\ \bmod x^{i+1}$ を満たす$i$ 次以下の多項式 $g_i$ を考えることにします。

あらためて行う処理を掲載します。

0. $f_{i-1} \equiv (g_{i-1}+px^{i})e^{kx} \bmod x^{i+1}$ を満たす $p$ を求める
1. $[x^j]f_{1,i} = (i-j)[x^j]f_{i-1}$ となるように $i$ 次以下の多項式 $f_{1,i}$ を定める
2. $[x^j]f_{2,i} = \frac{1}{i+Aj}[x^j]f_{1,i}$ となるように $i$ 次以下の多項式 $f_{2,i}$ を定める
3. $[x^j]f_{i}=[x^j]f_{2,i} \times e^x$ となるように $i$ 次以下の多項式 $f_i$ を定める

$0$ 番目の処理は $f$ の次数が大きくなるのに合わせて $g$ の精度を上げる処理です。

各処理を $g_i$ についての処理に言い換えます。 $0$ 番目の処理は $O(N+\log{\mathrm{mod}})$ 時間でできます。 $3$ 番目の処理は単に $k$ をインクリメントするだけです。

問題は $1,2$ 番目の処理です。まず $1$ 番目の処理は

$$f_{1,i} = if_{i-1} - x \frac{d}{dx}f_{i-1}$$

と考えることができ、 $f_{i-1} \equiv (g_{i-1}+px^{i})e^{kx} \bmod x^{i+1}$ の両辺を微分して考えれば

$$g_{1,i} \equiv ig_{i-1}- x\frac{d}{dx}g_{i-1} \bmod x^{i+1}$$

と処理すればいいことが分かります。これは $O(N)$ 時間で計算できます。

次に $2$ 番目の処理ですが、これは

$$f_{2,i}(x^A) = x^{-i}\int_{0}^{x}t^{i-1}f_{1,i}(t^A)dt$$

を満たす $f_{2,i}$ を求めると考えることができます。これは $g$ の式で考えると

$$\frac{d}{dx}(x^{i}g_{2,i}(x^A)e^{kx^A}) \equiv x^{i-1}g_{1,i}(x^A)e^{kx^A} \bmod x^{i+1}$$

を満たす $g_{2,i}$ を求めることと同じで、

$$g_{1,i} \equiv ig_{2,i} + Ax\frac{d}{dx}g_{2,i}+kAxg_{2,i} \bmod x^{i+1}$$

が成り立つので、係数比較すると低次の項から順に $O(N\log{\mathrm{mod}})$ 時間で求めることができます。この計算のボトルネックは $i+Aj$ の逆数を求める部分なので、これをまとめて求めるようにすると $O(N+\log{\mathrm{mod}})$ 時間で計算できます。

以上より $i=1,2,\dots,N-1$ の順に上記の処理を行って $g_{N-1} \bmod x^{N}$ を $O(N^2+\log{\mathrm{mod}})$ 時間で求めることができます。最後に $f_N$ の復元は愚直に畳み込むことで $O(N^2)$ 時間でできます。

なお、 $0$ 番目の処理で求めている $p$ についてなのですが、実は $1$ 番目の処理で $(i-i)$ が掛かるせいで消えるので求める必要はありません。

## 提出

(C++ 1338ms)

https://atcoder.jp/contests/arc180/submissions/55137567