! https://zhuanlan.zhihu.com/p/617710174
2023年3月28日16:56
下午在研究群论,又看了一会行列式
看到了“行列式展开式前的系数与排列的逆序对或者奇偶性有关”,猛地回想起1年前做的“萨姆·洛伊德‘14-15’游戏”(题目叫奇数码)
和刚刚看的群伦里置换奇偶性的定义
每个置换都可以写成对换的乘积。
一个置换若只能写成偶数对换的乘积则成为偶的; 一个置换若只能写成奇数对换的乘积则成为奇的
而根据我的总结, 一个置换写成多少个对换成积是看能连成几个环,个数即为 n - 环的个数
如
$\left(\begin{array}{lllll}1 & 2 & 3 & 4 & 5 \ 1 & 4 & 3 & 5 & 2\end{array}\right) $
即圈(置换的另一种符号) (2 4 5)
1 -> 1
4 -> 5
3 -> 3
5 -> 4
2 -> 5
有三个环 (1) (3) (2 4 5)
即这个置换可以写成 2 个对换的乘积 (2 4) (2 5) 注意,这并不唯一
突然!一道灵光闪现, 似乎打通了任督二脉,豁然开朗,将三个知识串,不,契合在一起,此之谓融会贯通呼!
于是我大胆验证我的猜想, 一个排列的逆序对个数奇偶性与置换的奇偶性相同。
好 ,开始coding
int N;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int fuct(vector<int> &v, int l, int r) {
if (l >= r) return 0;
ll mid = (l + r) / 2;
ll res = fuct(v, l, mid) + fuct(v, mid + 1, r);
int i = l, j = mid + 1, id = l;
while(i <= mid && j <= r){
if (v[i] <= v[j]) a[id++] = v[i++];
else a[id++] = v[j++], res += (mid - i + 1);
};
while(i <= mid) a[id++] = v[i++];
while(j <= r) a[id++] = v[j++];
for (int k = l; k <= r; k++) v[k] = a[k];
return res;
}
int vis[maxn];
int solve() {
N = rng() % 1000 + 1000;
vector<int> permutation(N);
for (int i = 0; i < N; i++)
permutation[i] = i, vis[i] = 0;
shuffle(permutation.begin(), permutation.end(), rng);
vector<int> T = permutation;
int A1 = fuct(T, 0, N - 1); // 逆序对
int A2 = 0;
vector<int> V = p;
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
int now = i, cnt = 0;
while(!vis[now]) {
cnt++;
vis[now] = 1;
now = V[now];
}
A2 += cnt - 1;
}
// A2 是置换的对换乘积个数
if (A1 % 2 == A2 % 2) return 1;
else return 0;
}
signed main() {
#ifdef LOCAL
//freopen("w.in", "r", stdin);
//freopen("w.ans", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int cnt = 0;
while(cnt <= 10000) {
if (solve()) {
cout << "YES" << endl;
cnt++;
}
else {
cout << "NO" << endl;
break;
}
}
return 0;
}
不出意外,应该是10000个 “YES”
结果也不出意外, 0 个 “NO”
顺稍提一嘴, 奇数码那题将所有数顺着记录下来, 分别求出前后的逆序对数,判断是否同奇偶,若是,则可达。(“必要性好证,充分性要’长篇大论‘”,这是一年前我看的题解上这么写的)。
必要性确实好证,空格左右交换不会影响数组, 上下交换会使一个数向前移动 \(n-1\) 位,因为 \(n - 1\) 为偶数, 因为每次交换,逆序对 +1 或 -1 所以逆序对改变次数为偶数,故而不改变奇偶性。
充分性呢?
好吧, 置换的资料上显示,也很复杂,没给结论,留给以后的我去探究吧。