首页 > 其他 > 详细

poj 3105 Expectation 按位统计

时间:2017-07-16 10:52:00      阅读:180      评论:0      收藏:0      [点我收藏+]

题意:

给n,求sum(i^j)/(n^2),0<=i,j<n。n<10^9

分析:

暴力n^2算法肯定超时。这是logn按位统计算法:按位先算出0出现的个数x,则1出现的个数为n-x。再算每位对和的贡献。

代码:

//poj 3105
//sep9
#include <iostream>
using namespace std;

int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		int n;
		double ans=0;
		scanf("%d",&n);
		for(int i=0;i<31;++i){
			int s=1<<i;		
			double p=(((n-1)>>(i+1)<<i)+((n-1)&(s-1))+1)/(double)n;
			ans+=2*p*(1-p)*s;
		}	
		printf("%.2lf\n",ans);
	}
}
 


poj 3105 Expectation 按位统计

原文:http://www.cnblogs.com/lytwajue/p/7189804.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!