BZOJ-1011: [HNOI2008]遥远的行星

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1011

这里有个神奇的近似公式（传送门：http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7），然后就可以水过去了。。。不过BZOJ上面略坑C++精度啊，我用double在本地A了在OJ WA个不停，改称long double在本地WA了在OJ上却AC了额。。。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

 

using namespace std ;

 

#define ld long double

#define g( i ) ( int( a * ( ld )( i ) ) )

#define maxn 100100

 

int n , t ;

ld a , f[ maxn ] , m[ maxn ] ;

 

int main(  ) {

    scanf( "%d%llf" , &n , &a ) ;

    for ( int i = 0 ; i ++ < n ; ) scanf( "%llf" , m + i ) ;

    t = int( sqrt( n ) ) ;

    for ( int i = 0 ; i ++ < t ; ) {

        f[ i ] = 0 ;

        for ( int j = 0 ; j ++ < g( i ) ; ) f[ i ] += ( m[ j ] / ( ld )( i - j ) ) * m[ i ] ;

        for ( int j = i + t ; j <= n ; j += t ) {

            f[ j ] = ( f[ j - t ] / m[ j - t ] ) * ( ( ld )( j - t - g( j - t ) / ( ld )( 2 ) ) / ( ( ld )j - ( ld )g( j - t ) / ( ld )( 2 ) ) ) ;

            for ( int k = g( j - t ) ; k ++ < g( j ) ; ) {

                f[ j ] += ( m[ k ] / ( ld )( j - k ) ) ;

            }

            f[ j ] *= m[ j ] ;

        }

    }

    for ( int i = 0 ; i ++ < n ; ) printf( "%.10f\n" , double( f[ i ] ) ) ;

    return 0 ;

}