UVa 10883 超级平均数(二项式系数+对数计算)

时间:2021-04-17 15:14:38

https://vjudge.net/problem/UVA-10883

题意:

给出n个数,每相邻两个数求平均数,依次类推,最后得到1个数,求该数。

思路:

演算一下可以发现最后各个数的系数就是二项式系数。

但是n太大,直接计算会溢出。

所以,这里要用对数计算。(cmath中的log默认以e为底)

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std; int n; int main()
{
//freopen("D:\\input.txt","r",stdin);
int T;
scanf("%d",&T);
for(int kase=;kase<=T;kase++)
{
scanf("%d",&n);
double ans=,c=;
for(int i=;i<n;i++)
{
double x;
scanf("%lf",&x);
if(x>) ans+=exp(c+log(x)-(n-)*log());
else if(x<) ans-=exp(c+log(-x)-(n-)*log());
c=c+log(n-i-)-log(i+);
}
printf("Case #%d: %.3f\n",kase,ans);
}
return ;
}