题解：CF938E Max History

· · 题解

题意

给定数组 A。定义 f_{A} 为：

思路

总贡献类问题有两种思路：枚举方案算贡献和枚举贡献算方案。

显然对于每一个 A_i 计算它产生贡献的方案数是合理的。先转化题意：f(A) 就是严格前缀最大值除去最后一个元素的和。一个元素 A_i 产生贡献的充要条件是 A_i 是严格前缀最大值且不是最后一个严格前缀最大值，既 A_i 前面都比 A_i 小，且后面有比 A_i 大的。

先将 A 排序，不考虑重复，则比 A_i 小的有 i - 1 个，枚举 A_i 放在哪里，用式子表示上述方案数为：

\sum_{j = 0}^{i - 1} A(i - 1, j) \cdot (n - j - 1)!

然后是一些数学推导参考的题解，提出公共部分，得：

(i - 1)! \cdot \sum_{j = 0}^{i - 1} \frac {(n - j - 1)!} {(i - 1 - j)!}

把排列变组合，提出 (n - i)!，得：

(n - i)! \cdot (i - 1)! \cdot \sum_{j = 0}^{i - 1} \frac {(n - j - 1)!} {(i - 1 - j)! \cdot (n - i)!}

然后就很高兴地发现后面是组合数求和，朱世杰恒等式代进去：

(n - i)! \cdot (i - 1)! \cdot \begin {pmatrix} n \\ n - i + 1 \end {pmatrix}

最后对于每个 i 求一下即可。至于重复的数字可以记录第一次遇到的位置，此后重复的值的贡献都用这个位置算。具体可以见代码。

代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1000005, Mod = 1e9 + 7;
int A[N], Fac[N] = {1}, Inv[N] = {1};

int Pow(int x, int k) {
    int Res=1;
    for(;k;k>>=1, x=(ll)x*x%Mod) if(k&1)    Res=(ll)Res*x%Mod;
    return Res;
}

int C(int n, int m) {
    return (ll)Fac[n]*Inv[m]%Mod*Inv[n-m]%Mod;
}

int main() {
    int n;  cin>>n;
    for(int i=1;i<=n;i++)   Fac[i]=(ll)Fac[i-1]*i%Mod;
    Inv[n]=Pow(Fac[n], Mod-2);
    for(int i=n;i>=1;i--)   Inv[i-1]=(ll)Inv[i]*i%Mod;

    for(int i=1;i<=n;i++)   cin>>A[i];
    sort(A+1, A+1+n);

    int Ans=0;
    for(int i=1, Last=0;i<=n && A[i]!=A[n];i++) {
        if(A[Last]!=A[i])   Last=i;
        Ans=(Ans+(ll)A[Last]*Fac[n-Last]%Mod*Fac[Last-1]%Mod*C(n, n-Last+1))%Mod;
    }

    cout<<Ans<<endl;
    return 0;
}

/*
\sum_{j = 0}^{i-1} A_i*A(i-1, j)*(n-j-1)!
*/