在纸上演算一下就能看出答案是：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)
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = 50000 + 10; 5 const double ln2 = log(2.0); 6 double a[maxn], log_c[maxn]; 7 8 int main() 9 { 10 //freopen("in.txt", "r", stdin); 11 12 int n, T; 13 scanf("%d", &T); 14 log_c[0] = 0; 15 for(int kase = 1; kase <= T; kase++) 16 { 17 scanf("%d", &n); 18 for(int i = 0; i < n; i++) scanf("%lf", &a[i]); 19 n--; 20 double ans = 0; 21 for(int i = 1; i <= n; i++) log_c[i] = log_c[i-1] + log(n-i+1) - log(i); 22 23 for(int i = 0; i <= n; i++) 24 { 25 if(a[i] > 0) ans += exp(log_c[i] + log(a[i]) - n * ln2); 26 else if(a[i] < 0) ans -= exp(log_c[i] + log(-a[i]) - n * ln2); 27 } 28 29 printf("Case #%d: %.3f\n", kase, ans); 30 } 31 32 return 0; 33 }
原文：http://www.cnblogs.com/AOQNRMGYXLMV/p/4366954.html
