序列、排列的全排列的逆序对

1.

题目大意：

给一个长度为n的的数组a，n是1到1e5，ai是1到1e5，问a的所有排序的序列的逆序对之和，会有重复的数字出现

题目链接：https://ac.nowcoder.com/acm/contest/46597/E

typedef long long ll;
typedef long long LL;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef pair<double,double> pdd;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define endl '\n'
const int N = 1e5 + 7;
LL ksm(LL x, LL y) {
	LL res = 1;
	while (y) {
		if (y & 1) {
			res = 1ll * res * x % MOD;
		}
		x = 1ll * x * x % MOD;
		y >>= 1;
	}
	return res;
}
LL inv(int x) {
	return ksm(x, MOD - 2);
}
LL b[N], fac[N];
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin >> n;
	std::vector<LL>a(n + 1), s(n + 1), cnt(n + 1);
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
		b[i] = a[i];
	}
	if (n == 1) {
		std::cout << 0 << '\n';
		return 0;
	}
	std::sort(b + 1, b + 1 + n);
	int len = std::unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = std::lower_bound(b + 1, b + 1 + len, a[i]) - b;
		++cnt[a[i]];
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fac[i] = 1ll * fac[i - 1] * i % MOD;
	}
	LL ans = 0;
	for (int i = 1; i <= len; ++i) {
		s[i] = s[i - 1] + cnt[i];
	}
	for (int i = 1; i <= len; ++i) {
		ans = (ans + s[i - 1] * cnt[i]) % MOD;
	}
	std::cout << 1ll * ans * fac[n] % MOD * inv(2) % MOD << '\n';

	return 0;
}

2

题目大意：

求所有由1-9组成的长度为n的序列逆序对总数。会有重复的数字
题目链接：https://vjudge.net/problem/SCU-4571

思路: 直接算贡献, 也就是我们直接从9个里任选2人, 那么这两个就可以造成一个1的贡献, 那么其他地方了? 就可以随便填, 然后算出送的填的方式即可. 所以公式就是： \(C(n, 2) * C(9, 2) * 9^{n-2}\).
含义就是9个里任选选出了两个数, 可以造成贡献1, 那么方案是在n个位置中任选的两个位置去填这任选的两个数字, 然后其他位置可以9个数字任意填, 所以答案就是这么多.

注意取mod, 用unsigned long long 溢出自动取mod, 即自动取\(2^{64}\)的mod.

#define ull unsigned long long int
ull qpow(ull x, ull y) {
    ull res = 1;
    while(y) {
        if (y & 1) res = res * x;
        x *= x;
        y >>= 1;
    }
    return res;
}
void solve()
{
    ull n;
    cin >> n;
    ull ans = (n * (n-1) / 2) * (9 * 8 / 2) * qpow(9, n-2);
    cout << ans << endl;
}

3

题目大意：

求长为n的全部排列的逆序对的数量,这里是排列了
题目链接：https://vjudge.net/problem/SCU-4571

经典结论：长度为n的排列的逆序对数量的期望为\(C(n,2)/2\)。

简单证明：任意两个数在一个排列中，为逆序的概率是\((1/2)\)，选择两个数的方案为\(C(n,2)\)。
故长度为n的排列的逆序对数量的总和为n!*C(n,2)/2，其中，n!是排列的数量
例题：https://ac.nowcoder.com/acm/contest/45670/F