UVa 10883 (组合数 对数) Supermean

时间：2021-10-17 15:14:47

在纸上演算一下就能看出答案是：sum{ C(n-1, i) * a[i] / 2^(n-1) | 0 ≤ i ≤ n-1 }

组合数可以通过递推计算：C(n, k) = C(n, k-1) * (n-k-1) / k

但是n太大了，直接计算组合数会爆double的。所以计算的时候要取一下对数就行了，组合数对数的递推相应就变成了log_C(n, k) = log_C(n, k-1) + log(n-k-1) - log(k)

 #include <cstdio>

 #include <cmath>

 const int maxn =  + ;

 const double ln2 = log(2.0);

 double a[maxn], log_c[maxn];

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int n, T;

     scanf("%d", &T);

     log_c[] = ;

     for(int kase = ; kase <= T; kase++)

     {

         scanf("%d", &n);

         for(int i = ; i < n; i++) scanf("%lf", &a[i]);

         n--;

         double ans = ;

         for(int i = ; i <= n; i++) log_c[i] = log_c[i-] + log(n-i+) - log(i);

         for(int i = ; i <= n; i++)

         {

             if(a[i] > ) ans += exp(log_c[i] + log(a[i]) - n * ln2);

             else if(a[i] < ) ans -= exp(log_c[i] + log(-a[i]) - n * ln2);

         }

         printf("Case #%d: %.3f\n", kase, ans);

     }

     return ;

 }

代码君

相关文章