[ SPOJ ] RNG – Random Number Generator

题意:有n个正整数\(1 \leq x_1…x_n \leq 10\),\(a_i\)为\([-x_i,x_i]\)范围内的一个随机的实数,求\(a \leq \sum a_i \leq b\)的概率。\( (n \leq 10) \) 题解:这题有一个n=2的版本。 首先将a和b都加上\(\sum x_i\),那么问题中\(a_i\)范围变为\([0,2x_i]\)。和链接中的题目一样,考虑容斥。另外由于统计和在一个区间内难度比较大,所以就考虑和\( \leq b\)的概率减去和\( \leq a\)的概率。 设\(f(x)\)为\(0\leq a_1,a_2,a_3,\cdots,a_n\leq x\)时\(\sum a_i\leq x\)的概率\(*x^n\)。n=1时概率为1,n=2时概率为\(\frac{1}{2}\),n=3时概率为\(\frac{1}{6}\),(可以结合图形来看,如n=3时表示的是由(0,0,0),(x,0,0),(0,x,0),(0,0,x)四点构成的三棱锥的体积)由此可以类推\(f(n)=\frac{x^n}{n!}\)。\(x\leq 0\)时\(f(x)=0\)。 先讨论n=2的情形。n=2时答案为\[\frac{f(a)-f(a-2x_1)-f(a-2x_2)+f(a-2x_1-2x_2)}{\prod{2x_i}}\] 即先计算\begin{aligned}0\leq a_1\leq a \\ 0\leq a_2\leq a \\ 0\leq a_1+a_2\leq a \end{aligned}的情况,减去\begin{aligned}2x_1\leq a_1\leq a \\ 0\leq a_2\leq a \\ 2x_1\leq a_1+a_2\leq a \end{aligned}的情况和\begin{aligned}0\leq a_1\leq a \\ 2x_2\leq…