题目做的模模糊糊,是参照他人的解题报告做的,其中有些公式还是不太明白.
不过,发现移位运算(<<,>>)比乘除优先级低,位运算(&)比比较运算符(==)要低.
参考的解题报告:
题目意思:
如果有两个随机数生成器A,B(生成数都小于输入值)
例如n=3;
A 000 001 010
B 000 001 010
两者再随机异或生成的３＊３＝９个数进行期望计算...
计算结果:
*** 000 001 010
000 000 001 010
001 001 000 011
010 010 011 000
求期望得到4/3.
由于数量庞大 10^9 直接模拟一定超时
所以直接计算每一位的 0 1 个数可以简化计算量
条件一:在异或中,只要两个位不同0 1或1 0 就能得到1
条件二:计算每一位的0 1出现的个数,例如上面,最低位(假设i为二进制权,i=1)1出现1次,
0出现3-1次所以表中得到最低位是1的个数就是1*2+2*1=4个,所以这一位贡献的期望值
是(1*2+2*1)*i/(3*3)=4/9;如此计算第二位,1出现1次,同样贡献期望值为(1*2+2*1)*i/(3*3)=8/9,
此时(i=2)；第三为i=4....
只要算出产生数中每一位的0 1个数k代入
2*(k*(n-k))*i/(n*n) ==> 2*p*(1-p)*i 其中 p=(n-k)/n 表示 0在该位出现的概率...
Source:
#include<iostream>
using namespace std;
int main()
{
long k,n,s,i;
double r,p;
for(cin>>k;k>0;--k)
{
cin>>n;
for(i=0,r=0;i<32;++i)
{
s=1<<i;
if(s>n)break;
p=((((n&s)==0)?n%s:s)+(n/s>>1)*s)/(double)n;
//高位全为0时:(((n&s)==0)?n%s:s)若s位为0,则有n%s个数,s位为0
//低位全为0时:n/s,然后除以2,s位以上的值,*s,s位为0,低位全为0的数的个数
r+=2*p*(1-p)*s;
//cout<<r<<endl;
}
printf("%.2lf/n",r);
}
return 0;
}
//#include <stdio.h>
//int main()
//{
// // freopen("in.txt","r",stdin);
// // freopen("out.txt","w",stdout);
// int t,i,n,s;
// double r,p;
// scanf("%d",&t);
// while(t--){
// scanf("%d",&n);
// r=0;
// for(i=0;i<32;i++){
// s=1<<i;
// p=((n/s>>1)*s+(((n&s)==0)?n%s:s))/(double)n;
// printf("%d,%d,%d/n",n,s,n/s>>1);
// //当前位确定0的个数 (n/s>>1)*s 可以理解为 n/2/s*s ==> n/2后再把 s 位以下的全部清为0
// // ((n&s)==0)?n%s:s)可以理解为 如果当前位为1，表示当前为位0的情况有s种，如果当前位为0，则只有n%s种
// //加起来的和就是 0 的个数了
// r+= 2*p*(1-p)*s;
// }
// printf("%.2lf/n",r);
// }
// return 1;
//}