実数 \(y\) (\(0 \leq y \leq 1\))，非負整数 \(n\) に対し，以下の手順が出力する値の期待値を \(a_n(y)\) とおきます．

• \(n\) 個の実数を \([0,1]\) の中で生成し，\(x_1,\cdots,x_n\) とおく， \(x_1 < \cdots < x_n < y\) でない場合，\(0\) を出力して終了する． \(x\) が昇順なら，\(\prod_{1 \leq i \leq n} (y^A+\sum_{i < j \leq n} x_j^A)\) を出力して終了する．

\(f(y,x)=\sum_{0 \leq n} a_n(y)x^n\) とおきます． 後でわかることですが \(a_n(y)\) は \(y\) の多項式になり，\(f\) は \(2\) 変数形式的べき級数として定義できます．しかしひとまずは上の形式的な和として \(f\) を定義して話を進めます． 最終的に求めたいのは \(N! [x^N]f(1,x)\) です．

各 \(i\) について \(y^A, x_{i+1}^A, \cdots x_N^A\) のなかから一つの項を選び，それらの積を計算する，という手順を考えます． ある \(i\) について \(x_j^A\) を選んだ場合，\(i \to j\) と矢印を書くことにします． \(y^A\) を選んだ場合は \(i \to *\) と矢印を書くことにします． \(*\) は適当に用意した頂点です． すると木ができます．

この木を考えることで \(f\) が満たす方程式が求められます． \(*\) の直接の子の部分木ごとに問題を分解します． ある子 \(v\) を根とする部分木の”重み”について考えます． 頂点 \(v\) に対応する実数 \(t\) が \(0 \leq t \leq y\) を動くことを考えると，この部分木の重みは

\(y^A x \int_{0 \leq t \leq y} f(t,x) dt\)

になります．\(y^A\) は \(v \to *\) 辺の重みで，\(x\) は \(v\) を頂点数として数えるための項です．

\(*\) が \(k\) 個の子を持つ場合，一旦部分木に順序をもたせて計算したあと \(1/k!\) 倍の係数をかければ良いです． 結局，\(f\) は以下の方程式を満たすとわかります．

\(f(y,x)=exp(y^A x \int_{0 \leq t \leq y} f(t,x) dt)\)

ここから \(a_n(y)\) が \(n=0,1,\cdots\) の順に求まって，さらにそれは \(y\) の多項式だとわかります．

さらによく観察すると，\(a_n(y)\) は \(y^{(A+1)n}\) の定数倍になっていることがわかります．

そこで \(z=y^{A+1}x\) とおくと，ある形式的べき級数 \(g(z)=\sum_{0 \leq n} b_n z^n\) を用いて \(g(z)=f(x,y)\) と書くことができます． 上で得た \(f\) の方程式を \(g\) で書き直すと，

\(g(z)=exp(\sum_{0 \leq n} \frac{b_n}{(A+1)n+1} z^{n+1})\)

となります．

\(exp\) の中の式を \(h(z)\) とおきます．

\([z^n] g\) がわかると \([z^{n+1}] h(z)\) がわかり，それを元に \([z^{n+1}] g(z)\) が計算できる，という風にして \(g\) の係数が小さい方から求まっていきます． \(N\) 回 \(exp\) を計算するのが最も直感的な方法ですが，これだと計算量が \(O(N^2 \log N)\) になり，実行時間制限に間に合いません．

そこでもう少し賢い方法で \([z^{n+1}] g(z)\) を計算してみます．\(\frac{d}{dz}g=\frac{d}{dz}exp(h)=\frac{d}{dz}h \times exp(h)=\frac{d}{dz}h \times g\). の \([z^n]\) の係数を考えると，\([z^{n+1}] g(z)\) の計算が \(O(n)\) で行えます．

よってこの問題は全体で \(O(N^2)\) 時間で解けます．

回答例(C++)