记录编号	101187	评测结果	AAAAAAAAAA
题目名称	[SPOJ 2002] 随机和生成器	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2014-05-10 16:58:25	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int SIZEN=2010;
ll n,a,b;
ll X[SIZEN]={0};
ll fact[SIZEN]={0};//fact[i]=i!
ll lg2[SIZEN]={0};//lg2[2^i]=i
ll sum,vol;//sum是X之和,vol是样本空间大小
void init(void){
	fact[0]=1;
	for(int i=1;i<=10;i++) fact[i]=fact[i-1]*i;
	for(int i=0,j=1;i<=10;i++,j<<=1) lg2[j]=i;
}
double quickpow(ll a,ll b){
	if(a<=0) return 0;
	double ans=1;
	while(b){
		if(b&1) ans*=a;
		a*=a;
		b>>=1;
	}
	return ans;
}
ll lowbit(ll x){
	return x&(-x);
}
void work(void){
	double ans=0;
	int H=(1<<n);
	int sign=1;
	int p=0,q;//p(n位二进制)是当前的容斥状态,某一位0表示其范围从0到正无穷,否则就是从X到正无穷
	ans+=quickpow(b,n)-quickpow(a,n);//计算容斥状态为0的情况
	for(int s=1;s<H;s++){//此时,将p的lowbit(s)位取反,计算此后p代表的容斥状态
		//这是一个精巧的设计,可以用归纳法证明,在s遍历[1,2^n-1]时p亦能遍历[1,2^n-1]
		//参见这里: http://www.shuizilong.com/house/archives/spoj-2002-random-number-generator/
		sign*=-1;//由于改变了一位,1的个数必然改变了奇偶性
		int temp=lowbit(s);
		q=p,p^=temp;
		//X数组的下标是从0开始的
		if(p<q)	a+=X[lg2[temp]],b+=X[lg2[temp]];//这意味着把该位从1变成了0,a和b应当加上对应的x
		else a-=X[lg2[temp]],b-=X[lg2[temp]];
		ans+=sign*(quickpow(b,n)-quickpow(a,n));
	}
	ans/=fact[n],ans/=vol;
	printf("%.9lf\n",ans);
}
void read(void){
	scanf("%lld%lld%lld",&n,&a,&b);
	sum=0,vol=1;
	for(int i=0;i<n;i++){
		scanf("%lld",&X[i]);
		sum+=X[i],X[i]*=2,vol*=X[i];
	}
	//下面将问题转化成生成非负实数
	a+=sum,b+=sum;
	a=max(0LL,a),b=max(0LL,b);//过小就达不到了,不如设成0
	a=min(a,sum*2),b=min(b,sum*2);//过大也达不到,不如设成2sum
}
int main(){
	freopen("rng.in","r",stdin);
	freopen("rng.out","w",stdout);
	init();
	int T;
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}
	return 0;
}