526互联

Codeforces Round 845 (Div. 2) and ByteRace 2023 B. Emordnilap

发布时间 2023-09-05 21:22:53作者: zsxuan

给一个长为 \(n\) 的排列，对于它的每一个排列 \(p\) ，复制一份并 \(reverse\) 拼到原排列的后面得到 \(a = \left [p, p_{reverse} \right ]\) 。

求 \(p\) 的所有排列对应的 \(a\) 的逆序对数之和，结果对 \(1E9+7\) 取模。

逆序对贡献：

  • 考虑逆序对贡献时，通常考虑 \(1 \leq i < j \leq n\) ，从二元组 \((a_i, a_j)\) 的情况考虑贡献，得到通式再扫描线式考虑。

此处考虑逆序对，依旧考虑 \(1 \leq i < j \leq n\) 。

  • \(a_{n + 1, 2n}\) 由 \(a_{1, n}\) 得到，位置可以确定，考虑四元组更优。
  • \(p_i, p_j, p_j, p_i)\) 中，容易发现逆序对数量恒为 \(2\) 。

\(n\) 个数中选两个作为 \(p_i, p_j\) 即一个排列的所有四元组 \((p_i, p_j, p_j, p_i)\) 方案，\(\times 2\) 即该排列的逆序对数。
共有 \(n!\) 个排列，于是答案为模意义下的 \(2 \cdot \binom{n}{2} \cdot n! = n \times (n - 1)!\) 。

view 
#include <bits/stdc++.h>
const int mod = 1E9 + 7;
void solve() {
	int n; std::cin >> n;
	int fact_n = 1; for (int i = 1; i <= n; i++) fact_n = 1LL * fact_n * i % mod;
	std::cout << 2LL * n * (n - 1) / 2 % mod * fact_n % mod << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}