UVa 10883 Supermean 题解

· · 题解

题目大意

超级平均数，即平均数的平均数。假定有一个数列 s_{1\cdots n}，那么我们对 s 两两求平均数，而后对 s 两两求平均数的结果两两求平均数，……，直到只剩一个数。输出这个数。

题目思路

最烂的方式即模拟算法，复杂度 \mathrm O(n^2)。弃疗。

我们可以手动模拟一下 n=1,2,3,4 时的情形（其中 O 代表答案）：

n=1,O=a_1 n=2,O=\frac{1}{2}(a_1+a_2) n=3,O=\frac{1}{4}(a_1+2a_2+a_3) n=4,O=\frac{1}{8}(a_1+3a_2+3a_3+a_4)

那么系数就是二项式定理给出的三角形

1 1\ 1 1\ 2\ 1 1\ 3\ 3\ 1

无疑。

那么，我们就可以改写 O 的式子：

O=\frac{1}{2^{n-1}}\sum_{1\le i\le n}\binom{n-1}{i-1}a_i

计算它所需的时间是 \mathrm O(n)，因为我们可以用

\binom{n}{m+1}=\frac{n-m}{m+1}\binom{n}{m}

使得组合数与 a_k 可以同步使用。

这是因为，

\binom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{(m+1)\times(m+2)\times\cdots\times n}{1\times2\times3\times\cdots\times (n-m)} \binom{n}{m+1}=\frac{n!}{(m+1)!(n-m-1)!}=\frac{(m+2)\times\cdots\times n}{1\times2\times3\times\cdots\times (n-m-1)}

这样，我们就可以用手推导出它们的比值

\binom{n}{m+1}\left/\binom{n}{m}=\frac{n-m}{m+1}\right.

不幸的是由于 n\le 5\times 10^4，它的精度非常低，怎么办呢？

参考了几篇题解，他们使用了对数作为提高精度的工具。这里采用符号 \mathrm{Pw}(a,b)=a^b 来替代部分数学符号，因为把一大串式子写在幂上实在不太好。

那么我们就可以改写原来的式子：

=\sum_{1\le i\le n}\binom{n-1}{i-1}\frac{a_i}{2^{n-1}} \log_2|a_i|-\log_2(n-1)\right]

虽然式子很长，但是它使用了对数来保证精度。

当然，随着我们使用对数，我们也得把增长贼快的二项式系数改作如下形式：

\log_2\binom{n}{m+1}=\log_2\binom{n}{m}+\log_2\frac{n-m}{m+1}

那么我们就可以只计算 a 的对数并把指数加在答案上就好了。

代码如下。

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
long double sgn(long double x){
    if(x>0) return 1.0;
    if(x<0) return -1.0;
    return 0.0;
}
void maintain(int __){
    int n;
    long double a[50010],ans=0.0,lbinom=0.0;
    cin>>n,n--;
    for(int i=0;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++){
        ans+=sgn(a[i])*pow(2.0,lbinom+log2(fabs(a[i]))-n);
        // binom*=(n-i),binom/=(i+1);
        lbinom+=log2((double)(n-i)/(double)(i+1));
    }
    // cout<<endl;
    cout<<"Case #"<<__<<": "<<fixed<<setprecision(3)<<ans<<endl;
}
int main(){
    int t,_=0;
    cin>>t;
    while(t--) maintain(++_);
    return 0;
}

EOF