解説

方針

$x_1+x_2+\cdots+x_N=K$を満たす平面で$[0,1]^N$の超立方体をぶった切ったとき原点を含む方の体積は$[0,1]$から一様ランダムに$N$個実数を選んだときの総和が$K$以下となる確率と等しいので、以下その確率を計算する。

確率変数の定義

$[0,1]$上の一様分布に従う$N$この独立な確率変数を$x_i (1\leq i \leq N)$とし、総和を$S_N$とする。各変数の確率密度関数$f(x)$は$0\leq x \leq 1$となる関数、すなわち$f(x)=U(x)-U(x-1)$である。 $N=i$のときの確率密度関数を$f_i$とする。

畳み込み

$N=2$のとき確率密度関数は、足して$x$になるように畳み込み、以下のようになる。

$$f_2(x) = \int_{-\infty}^\infty f_1(t)f_1(x-t) dt$$

$N=3$では$f_2(x)$と$f_1(x)$の畳み込みである。$N>3$でも同様。

ここで、

$$\begin{align*} \mathcal{L}[f_n(x)](s)&=\mathcal{L}[f_{n-1}(x)*f_1(x)](s) \\ &=\mathcal{L}[f_{n-1}(x)](s)\mathcal{L}[f_1(x)](s) \\ \end{align*}$$

となり再帰的に適用すれば

$$\begin{align*} \mathcal{L}[f_n(x)](s)&=(\mathcal{L}[f_1(x)](s))^N \\ &=\left(\frac{1-e^{-s}}{s}\right)^N\\ &=\frac{(1-e^{-s})^N}{s^N}\\ &=\frac{\sum_{k=0}^{N}(-1)^k \binom{N}{k}e^{-ks}}{s^N} \end{align*}$$

となる。これを逆ラプラス変換すると、

$$\begin{align*} \mathcal{L}^{-1}\left[\frac{\sum_{k=0}^{N}(-1)^k \binom{N}{k}e^{-ks}}{s^N}\right](x)&= \frac{1}{(N-1)!}\sum_{k=0}^{N} (-1)^k \binom{N}{k} (x-k)^{N-1}U(x-k) \end{align*}$$

求めるものはこれの$[0,K]$上定積分の値なので、

$$\begin{align*} &\int_{0}^{K}\frac{1}{(N-1)!}\sum_{k=0}^{N} (-1)^k \binom{N}{k} (x-k)^{N-1}U(x-k) dx\\ =&\left[\frac{1}{N!}\sum_{k=0}^{K} (-1)^k \binom{N}{k} (x-k)^{N}U(x-k)\right]_{0}^{K}\\ =&\frac{1}{N!}\sum_{k=0}^{K} (-1)^k \binom{N}{k} (K-k)^{N} \end{align*}$$

あとは適切に実装すればよいです。全体として$O(N\log N)$で解けて十分高速です。