E. Max History 题解

一、题目回顾

给定长度为 $n$ 的数组 $a$，定义 $f_a$：

• 初始 $f_a = 0$，$M = 1$
• 对 $i = 2 \dots n$，若 $a_M < a_i$，则 $f_a = f_a + a_M$，然后 $M = i$

求 $f_a$ 在所有 $n!$ 种排列下的总和，对 $10^9+7$ 取模。

二、组合分析

2.1 过程的意义

扫描排列时，$M$ 始终指向当前遇到的最大值。每当遇到一个严格更大的元素时，旧的最大值被累加到 $f_a$ 中，然后更新 $M$。

因此 $f_a$ 等于：排列中所有前缀最大值（prefix maximum）的前驱之和。换言之，除了全局最大值外，每个曾经成为前缀最大值的元素都会贡献一次自身的值。

2.2 一个元素何时贡献

考虑值 $v$ 的某个具体副本。它在排列中贡献 $v$ 当且仅当：

1. 所有严格大于 $v$ 的元素都出现在它之后（否则它无法成为前缀最大值）；
2. 所有等于 $v$ 的其他副本也都出现在它之后（若前面已有一个等于 $v$ 的前缀最大值，则 $a_M \ge v$，条件 $a_M < v$ 不成立）。

令：

• $S_v$ = 值 $\ge v$ 的元素个数（即严格大于 $v$ 的个数 $+$ 等于 $v$ 的个数）；
• $cnt_v$ = 值等于 $v$ 的元素个数。

对于一个确定的 $v$ 副本，它需要排在其余 $S_v - 1$ 个元素（所有 $\ge v$ 的其他元素）之前。

在所有 $n!$ 种排列中，该副本恰好在这些 $S_v$ 个元素中排第一的排列数为：

2.3 总贡献

每个等于 $v$ 的副本贡献相同。共有 $cnt_v$ 个副本，因此所有值为 $v$ 的元素对总和的贡献为：

对所有非全局最大值的值 $v$ 求和即可。

三、算法步骤

1. 对数组 $a$ 排序。
2. 预处理阶乘 $n!$ 及逆元。
3. 遍历排序后的数组，将相同值分为一组：
   • 设当前组值为 $v$，出现次数 $cnt$；
   • 设值 $\ge v$ 的元素个数 $S = n - i + cnt$（其中 $i$ 为该组最后一个元素的下标，$n-i$ 为严格大于 $v$ 的元素个数）；
   • 若 $v$ 不是全局最大值（即 $S < n$ 或还有更大元素），则贡献：$$v \cdot cnt \cdot \frac{n!}{S}$$
4. 输出总和模 $10^9+7$。

四、复杂度

• 排序 $O(n \log n)$
• 预处理阶乘与逆元 $O(n)$
• 遍历分组 $O(n)$

总复杂度 $O(n \log n)$，可通过 $n \le 10^6$。

五、AC 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
const int mod = 1000000007;

int n;
int a[N];
int ft[N], ift[N];   // ft: 阶乘, ift: 阶乘逆元
typedef long long ll;

ll qp(ll x, int y) {
    ll ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);

    // 预处理阶乘
    ft[0] = 1;
    for (int i = 1; i <= n; i++)
        ft[i] = 1LL * ft[i - 1] * i % mod;

    // 预处理阶乘逆元
    ift[n] = qp(ft[n], mod - 2);
    for (int i = n; i >= 1; i--)
        ift[i - 1] = 1LL * ift[i] * i % mod;

    int cnt = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        ++cnt;
        if (a[i] < a[i + 1] && i < n) {
            // v = a[i], cnt = 当前组大小
            // S = n - i + cnt = 值 >= v 的元素个数
            // 贡献: v * cnt * n! / S
            int S = n - i + cnt;
            ans = (ans + 1LL * ft[n] * ft[S - 1] % mod 
                   * ift[S] % mod * a[i] % mod * cnt) % mod;
            cnt = 0;
        }
    }
    printf("%d\n", ans);
    return 0;
}

代码细节说明

• ft[n] * ft[S-1] % mod * ift[S] 等价于 $\frac{n!}{S}$，利用了 $ift[S] = (S!)^{-1}$ 以及 $ft[S-1] \cdot S = ft[S]$。
• 全局最大值（排序后最后一个元素）不会被处理，因为没有 $a_i < a_{i+1}$ 触发它的累计，其贡献自然为 $0$。