[ 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 a_2\leq a \\ 2x_2\leq a_1+a_2\leq a \end{aligned}的情况再加上重复减去的\begin{aligned}2x_1\leq a_1\leq a \\ 2x_2\leq a_2\leq a \\ 2x_1+2x_2\leq a_1+a_2\leq a \end{aligned}

上面三种情况显然可以等价于\begin{aligned}0\leq a_1\leq a-2x_1 \\ 0\leq a_2\leq a-2x_1 \\ 0\leq a_1+a_2\leq a-2x_1 \end{aligned}\begin{aligned}0\leq a_1\leq a-2x_2 \\ 0\leq a_2\leq a-2x_2 \\ 0\leq a_1+a_2\leq a-2x_2 \end{aligned}  \begin{aligned}0\leq a_1\leq a-2x_1-2x_2 \\ 0\leq a_2\leq a-2x_1-2x_2 \\ 0\leq a_1+a_2\leq a-2x_1-2x_2 \end{aligned}

上面的等价用到了变量不可能大于和以及将\(p\leq a_i\leq q\)等价变换为\(0\leq a_i-p\leq q-p\)这两个方法。

类似的n>2的情况也就是这么一回事了。


page views : 72 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注