\(L=1\) となるようにスケーリングしておきます． 便利のため，値域が \([-K,0]\) だと思うことにします．

赤いボールに書かれる数が \(r_1<r_2<\cdots<r_N\) で固定されているときのことを考えます．

青いボールに書かれる数を \(b_1 < b_2<\cdots<b_N\) とします． 満たすべき条件は \(r_i \leq b_i\) です． \(b_i\) を小さい方から決めていくことを考えると，以下のような積分を計算できればよいことがわかります．

• \(f_0(x)=1\)
• \(f_i(x)=\int_{t=r_i}^{x} f_{i-1}(t) dt\) (\(1 \leq i \leq N\))
• \(f_N(0)\) が答え

\(f_i(x)\) は全部多項式なので，その係数に対する漸化式が与えられていると考えることができます．

\(a_i=f_i(0)\) とおいて，\(a_0,\cdots,a_N\) に関する漸化式をまとめると，以下のようになります．

• \(a_0=1\)
• \(a_i=- \sum_{j=0}^{i-1}a_{j} \times r_i^{i-j}/(i-j)!\)

DPの順番を逆にしてみます． \(q_i=r_{N-i}\) として，以下の数列 \(b\) を計算したいことになります．

• \(b_0=1\)
• \(b_i=- \sum_{j=0}^{i-1}b_j \times q_j^{i-j}/(i-j)!\)

ここで，\(b\) の母関数 \(g(x)=\sum_{0 \leq i \leq N} b_i x^i\) を考えてみます．

すると，\(\sum_{0 \leq i \leq N} b_i x^i \exp(q_ix) \equiv 1 \mod x^{N+1}\) となります．

ところで，\(q_i\) は固定されておらず，候補が \(M\) 個あるのでした． \(q_i\) の候補を \(v_{i,1},\cdots,v_{i,M}\) として同様に DP を考えると，以下のような等式が成立します．

• \(\sum_{0 \leq i \leq N} b_i x^i (\frac{1}{M}\sum_{1 \leq j \leq M}\exp(v_{i,j}x)) \equiv 1 \mod x^{N+1}\)

ところで，\(v_{i,j}=(A_j-1)-i\) です．よって

• \(\sum_{0 \leq i \leq N} b_i x^i \exp(-ix) (\frac{1}{M}\sum_{1 \leq j \leq M}\exp((A_j-1)x)) \equiv 1 \mod x^{N+1}\)

となります．

ここで，\(V(x)=(\frac{1}{M}\sum_{1 \leq j \leq M}\exp((A_j-1)x))\) とおきます． すると，\(V(x) g(x \exp(-x)) \equiv 1 \mod x^{N+1}\) となります．

\(x \exp(-x)\) の compositional inverse を \(W(x)\) とおくと，

• \(g(x)=1/V(W(x)) \equiv 1 \mod x^{N+1}\)

となります．あとはこれを計算すればよいです．

\(V(X)\) の計算は，\(\sum_{1 \leq j \leq M} \frac{1}{1-(A_j-1)x}\) を分割統治+FFTで計算することに帰着できます．

残りのパートは，FPS の composition と compositional inverse そのものです．

全体計算量は \(O(M \log^2 M + N \log^2N)\) になります．

なお，手計算で \(W(x)=\sum_{1 \leq i} i^{i-1}/i! x^i\) と求めることにより，compositional inverse が省略できます．

回答例(C++)