首页 > 代码库 > uva - 10833 Supermean(二项式系数，对指数)
uva - 10833 Supermean(二项式系数，对指数)
模拟发现，每个元素求和时，元素的系数是二项式系数，于是ans=sum(C(n-1,i)*a[i]/2^(n-1)),但是n太大，直接求会溢出，其实double的范围还是挺大的，所以可以将组合数转化成对数:
e^(lnC(n-1, k)*A[k]/(2^n-1) ) ==> e^( ln C(n-1,k) + ln A[k] - (n-1)*ln2 );
又直接利用公式求二项式系数：C(n, k+1)/C(n, k) = (n-k)/(k+1);
而且对数还有递推求法:
logC(n,k+1)=logC(n,k)+log(n-k)-log(k+1)
代码:
1 #include <iostream> 2 #include <sstream> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <cctype>10 #include <algorithm>11 #include <cmath>12 #include <deque>13 #include <queue>14 #include <map>15 #include <stack>16 #include <list>17 #include <iomanip>18 19 using namespace std;20 21 #define INF 0xffffff722 #define maxn 5001023 const double tmp = log(2.0);24 double data[maxn];25 int main()26 {27 int T;28 scanf("%d", &T);29 for(int kase = 1; kase <= T; kase++)30 {31 int n;32 scanf("%d", &n);33 double ans = 0.0, c = 0.0;34 for(int i = 0; i < n; i++)35 {36 scanf("%lf", &data[i]);37 if(data[i] > 0) ans += exp(log(data[i]) - (n-1)*log(2.0) + c);38 else if(data[i] < 0) ans -= exp(log(-data[i]) - (n-1)*log(2.0) + c);39 //cout << ans << endl;40 c += log((double)n-i-1)-log((double)i+1);41 }42 printf("Case #%d: %.3lf\n", kase, ans);43 }44 return 0;45 }
uva - 10833 Supermean(二项式系数，对指数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。