2016-06-18

『Noi2016十连测第三场 - 哈夫曼树』

题目

问题描述

有这样一个经典问题：

给出一个长度为$n$的非负整数数组$a$。

每次可以选择数组中两个不同位置的数$a_i, a_j(i \neq j)$，将它们删除，然后再向数组中加入一个新的元素，值为$a_i + a_j$。

这样一次操作产生的代价是这个新元素的值，即$a_i + a_j$。

例如当前数组中的数为$a = \{1, 1, 3, 1\}$，选择$a_1 = 1, a_4 = 1$进行操作后，数组变为${1, 3, 2}$，代价为$2$。

一共会进行$n - 1$次操作，要求最小化代价之和。

这道题可以用经典的哈夫曼树算法解决，然而小D正在NOI考场上，根本不会哈夫曼树，他决定凭信仰出奇迹。

小D每次选数都是随机选两个数，随机规则为：

假如有三个数$x, y, z$，可能有相等的数，但是不影响选取。
小D会等概率选取$(x, y)(x, z)(y, z)$中的一对。

现在小D想知道他的程序的期望输出。

设期望输出为$ans$，为了避免精度误差，你只需要输出下述式子在模$10^9 + 7$域下的值。

$$ans \times \prod_{i = 2}^{n} \frac{i(i - 1)}{2}$$

输入格式

从文件huffman.in中读入数据。

第一行一个正整数$n$。

第二行$n$个非负整数$a_i$。

输出格式

输出到文件huffman.out中。

输出一个数表示答案。

样例输入1

5
1 2 2 3 3

样例输出1

样例输入2

点击这里下载

样例输出2

点击这里下载

数据规模

对于$20\%$的数据，$n \leq 5$。

对于另$10\%$的数据，数组$a$中最多只有$5$个正整数。

对于另$10\%$的数据，数组$a$中的数全部相同。

对于另$30\%$的数据，$n \leq 10^3$。

对于$100\%$的数据，$2 \leq n \leq 10^5$，$0 \leq a_i \leq 1000$。

题解

（稍后再补）

代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll sum;
int n;
ll ans;
ll power(ll x, ll p)
{
    if (p == 0)
        return 1;
    if (p == 1)
        return x % MOD;
    ll t = power(x, p / 2);
    t = (t * t) % MOD;
    if (p & 1)
        return t * x % MOD;
    else
        return t;
}
inline ll getrev(ll x)
{
    return power(x, MOD - 2);
}
ll s;
int main()
{
	freopen("huffman.in", "r", stdin);
	freopen("huffman.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a;
        scanf("%d", &a);
        sum += a;
    }
    s = 1;
    for (int i = 2; i <= n; i++)
        s = (s * i) % MOD * (i - 1) % MOD * getrev(2) % MOD;
    for (int i = n; i >= 2; i--)
    {
        ll t = ((s * 2) % MOD * getrev(i) % MOD) % MOD;
        ans += sum * t % MOD;
        ans %= MOD;
    }
    printf("%lld\n", ans);
}