题意:
给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);}
}