CodeForces 938E Max History 题解

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

新老客户大回馈,云服务器低至5折

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

补充:第一次写博客,如有不足,欢迎指出。

  

 


原文链接:https://www.cnblogs.com/cautx/p/10842034.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:kuangbin带你飞---数论基础

下一篇:P1491 集合位置