当前位置: 代码迷 >> 综合 >> poj 3105 Expectation 按位统计
  详细解决方案

poj 3105 Expectation 按位统计

热度:2   发布时间:2024-01-19 05:35:05.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);}
}