高旗超载乐队,19寸壁纸,微信刷票诚信雪彤认准
参考自：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 }
补充：第一次写博客，如有不足，欢迎指出。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论