Posted on 2009-03-28 23:07
杜仲当归 阅读(383)
评论(0) 编辑 收藏 引用
著名的分形思想。统计一个区间的时候，将[0, 1101)（前闭后开）分成[0,1000)和[1000, 1101)两段，前者通过二分缩小，每次都能得到定长的区间；后者不断寻找第一个1并划分，如例子中可分为[1000, 1100), [1100, 1101)。[1000,1100)去除前两位10后仍然是定长区间，因此能够很快统计。
#include <cstdio>
#include <string>
int T, X, Y;
int b[32][32];
int C ( int n, int m )
{
if ( n == 0 )
return 1;
if ( b[n][m] )
return b[n][m];
return b[n][m] = m * C ( n - 1, m - 1 ) / n;
}
int bitlen ( int n )
{
return n ? bitlen ( n >> 1 ) + 1 : 0;
}
double calc ( int n )
{
if ( n == 1 )
return 0;
if ( n == 2 )
return 1;
double ans = 1;
int len = bitlen ( n );
int i, j;
for ( i = len - 1; i >= 2; i -- ) // 总长度
{
for ( j = 1; j <= i; j ++ )
{
int t = C ( j - 1, i - 1 );
ans += double ( t ) * j / i;
}
}
int l = 1;
for ( i = len - 1; i >= 1; i -- )
{
if ( n & ( 1 << i - 1 ) )
{
for ( j = l; j <= len; j ++ )
{
int t = C ( j - l, i - 1 );
ans += double ( t ) * j / len;
}
l ++;
}
}
return ans;
}
void proc ()
{
//printf ( "%.6f %.6f\n", calc ( Y + 1 ), calc ( X ) );
printf ( "%.6f\n", ( calc ( Y + 1 ) - calc ( X ) ) / ( Y - X + 1 ) );
}
int main ()
{
//freopen ( "in.txt", "r", stdin );
//freopen ( "out.txt", "w", stdout );
memset ( b, 0, sizeof ( b ) );
scanf ( "%d", &T );
int i;
for ( i = 0; i < T; i ++ )
{
scanf ( "%d%d", &X, &Y );
proc ();
}
return 0;
}