题意：

给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);

	}

}