[SPOJ]RNG - Random Number Generator

题意：有n个正整数\(1<=x_1...x_n<=10\)，\(a_i\)为\([-x_i,x_i]\)范围内的一个随机的实数，求\(a<=\sum a_i<=b\)的概率。\( (n<=10) \)

题解：这题有一个n=2的版本http://zarxdy34.is-programmer.com/posts/211522.html。

首先将a和b都加上\(\sum x_i\)，那么问题中\(a_i\)范围变为\([0,2x_i]\)。和链接中的题目一样，考虑容斥。另外由于统计和在一个区间内难度比较大，所以就考虑和<=b的概率减去和<=a的概率。

设\(f(x)\)为\(0<=a_1,a_2,a_3,\cdots,a_n<=x\)时\(\sum a_i<=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<=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<=a_1<=a \\ 0<=a_2<=a \\ 0<=a_1+a_2<=a \end{aligned}的情况，减去\begin{aligned}2x_1<=a_1<=a \\ 0<=a_2<=a \\ 2x_1<=a_1+a_2<=a \end{aligned}的情况和\begin{aligned}0<=a_1<=a \\ 2x_2<=a_2<=a \\ 2x_2<=a_1+a_2<=a \end{aligned}的情况再加上重复减去的\begin{aligned}2x_1<=a_1<=a \\ 2x_2<=a_2<=a \\ 2x_1+2x_2<=a_1+a_2<=a \end{aligned}

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

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

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

#include <bits/stdc++.h>
using namespace std;

int x[10];
int n,a,b;
long double tot;

long double DFS(int o,int sum,int p)
{
	if (o==n)
	{
		if (sum<=0) return 0;
		long double res=1;
		for (int i=0;i<n;i++) res*=(long double)sum/(i+1);
		return res*p;
	}
	long double res=0;
	res+=DFS(o+1,sum,p);
	res+=DFS(o+1,sum-x[o],-p);
	return res;
}

int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		tot=1;
		scanf("%d%d%d",&n,&a,&b);
		int sum=0;
		for (int i=0;i<n;i++)
		{
			scanf("%d",&x[i]);
			a+=x[i],b+=x[i];
			x[i]*=2;
			sum+=x[i];
			tot*=x[i];
		}
		printf("%.9Lf\n",(DFS(0,b,1)-DFS(0,a,1))/tot);
	}
	return 0;
}