参考自：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 }
补充：第一次写博客，如有不足，欢迎指出。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/603503.html