首页 > > 程序设计 > C/C++ >

CodeForces 938E Max History 题解

2019-05-10 05:58:26来源：博客园阅读 ()

参考自：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 }