CodeForces 938E Max History 題解

參考自：https://blog.csdn.net/dreaming__ldx/article/details/84976834

　　　　https://blog.csdn.net/acterminate/article/details/79339494

題意：

　　給你一個數組，將數組裡的所有元素進行全排列，然後

藉助這兩個條件求出Σfa 即可。

分析：

　　n可以取到10^6，Time limit 是 3000 ms，直接枚舉有n!種情況，顯然優先認為這是個組合數學問題，找出一個通式本題即可AC。

　　從n個位置中挑出n-i+1（大於等於這個數的個數）個位置，這n-i+1個位置中這個數必須是第一位，其他數可以任意排列，即A(n-i,n-i)。然後把剩下的小於他的數插入剩下的空位，即C(n,n-i+1)*A(i-1,i-1)。化簡得A(n,n)/(n-i+1)。

　　最終結果就是：n!/(n-l+1)%mod 。

實現：現在就是求逆元的問題了。

關於逆元的知識可參考：https://www.cnblogs.com/Judge/p/9383034.html

附上AC代碼：

 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 #define mod 1000000007
 6 typedef long long ll;
 7 
 8 ll a[1000005];
 9 ll qp(ll a, ll b)
10 {
11     ll base = a, ans = 1;
12     while (b)
13     {
14         if (b & 1)
15         {
16             ans *= base;
17             ans %= mod;
18         }
19         base *= base;
20         base %= mod;
21         b >>= 1;
22     }
23     return ans;
24 }
25 int main()
26 {
27     ll n;
28     cin >> n;
29     for (ll i = 1; i <= n; i++)
30     {
31         cin >> a[i];
32     }
33     ll fac_n = 1;
34     for (ll i = 2; i <= n; i++)
35     {
36         fac_n *= i;
37         fac_n%=mod;
38     }
39     sort(a+1, a + n+1);
40     ll ans = 0, now;
41     for (ll i = 1; i <= n; i = now)
42     {
43         now = i;
44         while (a[i] == a[now] && now <= n)
45             now++;
46         if (now <= n)
47         {
48             ans = (ans + fac_n * qp(n - i + 1, mod - 2) % mod * (now - i) % mod * a[i] % mod)%mod;//乘(now-i)是因為有(now-i)個a[i]情況相同。
49         }
50     }
51     cout << ans%mod << endl;
52 }

補充：第一次寫博客，如有不足，歡迎指出。