题解：CF938E Max History
GavinCQTD
·
·
题解
根据题意，当一个点前面全比它小，后面有比它大的，它就能做出一个贡献。
那对于一个点，我们二分出有多少个点是大于等于它的（包含其本身），设这个数量为 $x$，那这个点做出的贡献就是这 $x$ 个点在满足当前点在最前面的情况下的摆放方式之和。
那就可以直接列出式子了。设第 $i$ 个点做出了 $f_i$ 次贡献。
$$f_i = \binom{n}{x} \times (x-1)! \times (n-x)!$$
上面的第二项之所以是 $(x-1)!$ 而不是 $x!$ 是因为当前点已经固定在最前面了。
$$Ans = \sum^{n}_{i=1} f_i \times a_i$$
注意最大值的 $f_i = 0$。
复杂度是 $O(n \log n)$ 的，过了。
```cpp
/******************************
- @GavinCQTD
- "E. Max History"
- # https://codeforces.com/problemset/problem/938/E
- 3000 ms
******************************/
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int MOD=1e9+7;
int n,a[1000005],b[1000005],x[1000005],mx=0;
ull fac[1000005];
ull qpow(ull a,ull b,ull P){
ull res=1;
while(b!=0){
if(b&1){
res = res*a%P;
}
a = a*a%P;
b >>= 1;
}
return res;
}
ull inv(ull x,ull P){
return qpow(x,P-2,P);
}
ull C(ull a,ull b){
return (fac[a]*inv(fac[a-b],MOD)%MOD)*inv(fac[b],MOD)%MOD;
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
b[i] = a[i];
mx = max(mx,a[i]);
}
sort(b+1,b+n+1);
fac[0] = 1;
for(int i=1;i<=n;i++){
fac[i] = fac[i-1]*i%MOD;
}
for(int i=1;i<=n;i++){
int l=1,r=n,rk=0;
while(l<=r){
int mid=(l+r)>>1;
if(b[mid]<a[i]){
rk = mid;
l = mid+1;
}
else{
r = mid-1;
}
}
x[i] = n-rk;
}
ull ans=0;
for(int i=1;i<=n;i++){
if(a[i]==mx){
continue;
}
ans += ((fac[x[i]-1]*fac[n-x[i]]%MOD)*C(n,x[i])%MOD)*a[i]%MOD;
ans %= MOD;
}
cout << ans << "\n";
return 0;
}
```