很好的一道题啊,学到了不少东西!!!!
首先是一个结论
逆序对总数 = n! / 2 * 不相等的数字对数
(1) 不相等的数字对数怎么求
结论 不相等的数字对数 = C(n,2) - ∑C(2,cnt(i))(i数字的出现次数)
(2) n! / 2 怎么处理,有取模的除运算怎么处理???
这块一直不会,今天一学才发现,就是之前学过的乘法逆元,学过就忘,不愧是我(doge
这里只说怎么处理,证明之类的不写了
a / b % mod 的情况,可以求b的乘法逆元
下面是两种求法
(1) p为质数
b的乘法逆元 x = qpow(b,mod - 2,mod),费马小定理,注意是mod - 2
(2)p不是质数
那么就得用扩展欧几里得算法了
实现代码
void Exgcd(int a, int b, int& x, int& y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
对于求 a / b % mod的问题 用扩展欧几里得算法
各参数含义:
a: 这里的a其实是a / b里的b
b:这里的b其实是p
x:要求的逆元
y:不知道
注意,扩展欧几里得是可以有返回值的,这个返回值的意义就是a,b的gcd
其实是exgcd(b,p,逆元x,路人y) return = b,p的gcd,不过这里用不到
求出逆元以后,就可以用 n! * 逆元 * 求出的不相等的数字数 % mod了
// Problem: 排队
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/46597/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Date: 2024-03-14 21:21:51
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define endl '\n'
#define int int64_t
using namespace std;
int a[100005],rec[100005];
const int mod = 1e9 + 7;
int fac(int x) {
if (rec[x]) return rec[x];
if (x == 0)
return rec[0] = 1;
return
rec[x] = (fac(x - 1) * x) % mod;
}
int qpow(int a,int b) {
int res = 1;
while (b) {
if (b & 1)res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
int C2(int x) {
return x * (x - 1) / 2;
}
void exgcd(int a,int b,int&x ,int& y) {
if (!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= a / b * x;
}
void solve() {
int n; cin >> n;
fac(n);
unordered_map<int, int>p;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[a[i]]++;
}
//逆序对总数 = n! / 2 * 不相等的数字对数
int x, y;
exgcd(2,mod, x, y);
x = (x % mod + mod) % mod;
int l = (rec[n] * x) % mod;
/*cout << "x = " << x << endl;
cout << "rec[n] = " << rec[n] << endl;*/
int r = C2(n);
for (auto k : p) {
r -= C2(k.second);
}
/*cout << "l = " << l << endl;
cout << "r = " << r << endl;*/
cout << l * r % mod << endl;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
标签:return,61,int,exgcd,牛客,逆元,小白月赛,rec,mod
From: https://blog.csdn.net/aiwangyi6/article/details/136723399