题意：

给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 
     
      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+1)<