CodeForces 938E Max History 题解
程序员文章站
2022-07-10 23:44:09
参考自:https://blog.csdn.net/dreaming__ldx/article/details/84976834 https://blog.csdn.net/acterminate/article/details/79339494 题意: 给你一个数组,将数组里的所有元素进行全排列, ......
参考自: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 }
补充:第一次写博客,如有不足,欢迎指出。
上一篇: 跟工厂合伙开公司是很蠢的想法
下一篇: spring cloud各种超时时间设置