No.302

$N$ がある程度小さいときは DP で求める.

サイコロを $i$ 個振ったときに出た目の和が $j$ になる確率を $p(i, j)$ とすると,

$$p(i, j) = \sum_{d=1}^6 \frac{p(i-1, j-d)}{6}$$

となる.

$N$ がある程度大きいときは中心極限定理を使って和の確率を正規分布とみなす.

サイコロ1つの場合は $\mu = 7/2$, $\sigma^2 = 35/12$ であるので, 和の場合は $\mu = 7/2 \cdot N$, $\sigma^2 = 35/12 \cdot N$ となる.

正規分布の累積分布関数は,

$$\frac{1}{2} \left(1 + \mathrm{erf} \frac{x-\mu}{\sqrt{2\sigma^2}} \right)$$

であるので, $[x, y]$ の間の積分値は,

$$\mathrm{erf} \frac{y-\mu}{\sqrt{2\sigma^2}} - \mathrm{erf} \frac{x-\mu}{\sqrt{2\sigma^2}}$$

で求められる.

なお, $[L, R]$ の積分を求めるのではなく, $[L-0.5, R+0.5]$ の積分を求めるようにする.