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代码：

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define mod 1000000007

 typedef long long ll;

 ll a[];

 ll qp(ll a, ll b)

 {

     ll base = a, ans = ;

     while (b)

     {

         if (b & )

         {

             ans *= base;

             ans %= mod;

         }

         base *= base;

         base %= mod;

         b >>= ;

     }

     return ans;

 }

 int main()

 {

     ll n;

     cin >> n;

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

     {

         cin >> a[i];

     }

     ll fac_n = ;

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

     {

         fac_n *= i;

         fac_n%=mod;

     }

     sort(a+, a + n+);

     ll ans = , now;

     for (ll i = ; i <= n; i = now)

     {

         now = i;

         while (a[i] == a[now] && now <= n)

             now++;

         if (now <= n)

         {

             ans = (ans + fac_n * qp(n - i + , mod - ) % mod * (now - i) % mod * a[i] % mod)%mod;//乘(now-i)是因为有(now-i)个a[i]情况相同。

         }

     }

     cout << ans%mod << endl;

 }

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

巴特西

CodeForces 938E Max History 题解

最新文章

热门文章