[CF938E]Max History题解

题面

>CF传送门<

>洛谷传送门<

解法

显而易见，对于一个数\(a_i\)，若果它出现在\(f\)序列中，必定\(a_i\)之前的元素要小于\(a_i\)，我们设\(cnt_i\)为序列\(a\)中小于\(i\)的元素，

那么得到\(\sum_{i=1}^n a_i \times (\sum_{j=1}^{cnt_i+1} \frac{cnt_i!}{(j-1)!\times(cnt_i-j+1)!} \times (j - 1)! \times (n-j)!)\)

化简得\(\sum_{i=1}^n a_i \times (\sum_{j=1}^{cnt_i+1} \frac{cnt_i!}{(cnt_i-j+1)!} \times (n-j)!)\)

然后提出\(cnt_i!\)得\(\sum_{i=1}^n a_i \times cnt_i! \times ( \sum_{j=1}^{cnt_i+1} \frac{(n-j)!}{(cnt_i-j+1)!})\)

提取一个\((n-cnt_i-1)!\)得\(\sum_{i=1}^n a_i \times cnt_i! \times (n-cnt_i-1) \times ( \sum_{j=1}^{cnt_i+1} (^{n-j}_{n-cnt_i-1}))\)

又可得\(\sum_{i=1}^n a_i \times cnt_i! \times (n-cnt_i-1) \times (^n_{n-cnt_i})\)

所以答案为\(\sum_{i=1}^n \frac{a_i*n!}{n-l_i}\)

代码

#include <cstdio>

#include <algorithm>

#define ll long long

#define MOD 1000000007

using namespace std;

ll jc[1000005], jcr[1000005];

ll a[1000005];

int main(){

    int n; scanf("%d", &n);

    for(ll i = 1; i <= n; ++i)

        scanf("%lld", &a[i]);

    jc[0] = jcr[n + 1] = 1;

    for(int i = 1; i <= n + 1; ++i)

        jc[i] = (jc[i - 1] * i) % MOD;

    for(int i = n; i >= 1; --i)

        jcr[i] = (jcr[i + 1] * i) % MOD;

    sort(a + 1, a + n + 1);

    ll ans = 0; int cur_val = 0, cnt = 0;

    for(int i = 1; a[i] != a[n]; ++i){

        (a[i] == a[i - 1]) ? (++cnt) : (cur_val += cnt, cnt = 1);

        ans += (((jc[n - cur_val - 1] * jcr[n - cur_val + 1]) % MOD) * a[i]) % MOD, ans %= MOD;

    }

    printf("%lld", ans); return 0;

}

巴特西

[CF938E]Max History题解

最新文章

热门文章