数论，与poj 3252差不多，数学题挺麻烦的，要认真再认真
#include<iostream> #include<cstdio> using namespace std; int c[31][31],binary[31]; int len; void init(int x) { int tx=1; len=0; while(tx<=x) { len++; tx=tx<<1; } for(int i=len;i>=1;i--) { binary[i]=x&1; x=x>>1; } return ; } double solve(double n,int x) { double ans=1/n; if(x==0||x==1) return 0.0; int i,j,k=1; for(i=2;i<=len-1;i++) for(j=0;j<=i-1;j++) ans+=(1+j)*c[i-1][j]/(i*n); for(i=2;i<=len;i++) { while(binary[i]==0&&i<=len) i++; for(j=0;j<=len-i;j++) ans+=(k+j)*c[len-i][j]/(len*n); k++; } return ans; } int main() { int i,j,ca; double ri,rj; for(i=0;i<31;i++) c[i][0]=c[i][i]=1; for(i=0;i<31;i++) for(j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; scanf("%d",&ca); while(ca--) { scanf("%d%d",&i,&j); init(i); ri=solve(j-i+1,i); init(j+1); rj=solve(j-i+1,j+1); printf("%.6lf/n",rj-ri); } return 0; }
