连续段的期望

【问题描述】

小N最近学习了位运算，她发现2个数xor之后数的大小可能变大也可能变小，and之后都不会变大，or之后不会变小。于是她想算出以下的期望值：现在有 N个数排成一排，如果她随意选择一对l,r并将下标在l和r中间(包括l,r)的数(xor,and,or)之后，期望得到的值是多少呢？取出每一对l,r 的概率都是相等的。小G认为这太easy了，容易被你们水过去，因此你需要告诉他所有选择情况下，(xor,and,or)值的和。

【输入格式】

第一行1个正整数N。

第二行N个非负整数代表数列。

【输出格式】

共两行六个数。

第一行3个数，分别表示xor的期望，and的期望，or的期望，保留3位小数。

第二行3个数，分别表示xor的和，and的和，or的和。

【输入样例】

2

4 5

【输出样例】

2.750 4.250 4.750

11 17 19

【数据规模】

30%数据中1<=N<=1000

对于另外的30%数据数列中只包含0和1

对于100%的数据1<=N<=100000，数列中的数 <= 10^9

【样例解释】

l, r xor and or

1,1 4 4 4

1,2 1 4 5

2,1 1 4 5

2,2 5 5 5

每一组l,r取的概率都是相同的,xor=(4+1+1+5)/4=2.750 其他同理

【得分说明】

第一行三个数每个数正确得两分。

第二行三个数每个数正确得一分。

第二行三个数全部正确再得一分。

分析

考虑dp。

用\(f(n,31)\)表示以n为右端点的区间中，各个二进制位上的1的个数。

然后就可以很方便的转移。时间复杂度\(O(31n)\)

#include<bits/stdc++.h>

using namespace std;

template<class T>T read(T&x)

{

	T data=0;

	int w=1;

	char ch=getchar();

	while(!isdigit(ch))

	{

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

	{

		data=data*10+ch-'0';

		ch=getchar();

	}

	return x=data*w;

}

typedef long long ll;

const int N=1e5+7;

int n,a[N];

int f[N][31];

ll s1,s2,s3;

int main(){

	freopen("nine.in","r",stdin);

	freopen("nine.out","w",stdout);

//	cerr<<int(1<<30)<<endl;

	read(n);

	for(int i=1;i<=n;++i)

		read(a[i]);

// xor

	for(int i=1;i<=n;++i)

		for(int j=0;j<31;++j)

		{

			if(a[i]>>j&1)

				f[i][j]=(i-1-f[i-1][j])+1;

			else

				f[i][j]=f[i-1][j];

			s1+=(1LL<<j)*f[i][j];

//			cerr<<i<<" "<<j<<" f="<<f[i][j]<<endl;

		}

	s1*=2;

	for(int i=1;i<=n;++i)

		s1-=a[i];

//	cerr<<"s1="<<s1<<endl;

// and

	memset(f,0,sizeof f);

	for(int i=1;i<=n;++i)

		for(int j=0;j<31;++j)

		{

			if(a[i]>>j&1)

				f[i][j]=f[i-1][j]+1;

			else

				f[i][j]=0;

			s2+=(1LL<<j)*f[i][j];

		}

	s2*=2;

	for(int i=1;i<=n;++i)

		s2-=a[i];

// or

	memset(f,0,sizeof f);

	for(int i=1;i<=n;++i)

		for(int j=0;j<31;++j)

		{

			if(a[i]>>j&1)

				f[i][j]=i;

			else

				f[i][j]=f[i-1][j];

			s3+=(1LL<<j)*f[i][j];

		}

	s3*=2;

	for(int i=1;i<=n;++i)

		s3-=a[i];

	printf("%.3lf %.3lf %.3lf\n",double(s1)/n/n,double(s2)/n/n,double(s3)/n/n);

//	printf("%lld %lld %lld\n",s1,s2,s3);

	return 0;

}

巴特西

test20181219 连续段的期望

连续段的期望

分析

最新文章

热门文章