首页 > 代码库 > poj 3105 Expectation 按位统计
poj 3105 Expectation 按位统计
题意:
给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 按位统计
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。