Solution Of P10454 奇数码问题

Dr1fty · 2024-05-17 13:42:44 · 题解

Hint

考虑把这个 n\times n 的矩阵按行拆开，再计算逆序对（跟逆序对有什么关联？）。

Solution

先给结论。

考虑把这两个 n\times n 的矩阵按行拆成长度为 n^2-1 的序列（忽略空格），则我们会发现，两个状态能够相互转换当且仅当两个序列的逆序对个数奇偶性相同。

为什么？

考虑左右移动：
```
5 2 8       5 2 8
1 _ 3       1 3 _
4 6 7       4 6 7
```
我们发现，交换前序列为 \{5,2,8,1,3,4,6,7\}，而交换后也为 \{5,2,8,1,3,4,6,7\}。因此左右移动对逆序对个数没有影响。
考虑上下移动：
```
5 2 8       5 _ 8
1 _ 3       1 2 3
4 6 7       4 6 7
```
我们发现，交换前序列为 \{5,2,8,1,3,4,6,7\}，而交换后也为 \{5,8,1,2,3,4,6,7\}。因此上下移动相当于把改变的那个数移动了 n-1 位，因此原来与那个数形成的所有逆序对都变为了非逆序对，而原来与那个数形成的所有非逆序对都变为了逆序对。

我们进一步观察：
- 若在交换的数中有奇数个逆序对，则由于 n-1 为偶数，因此剩下奇数个非逆序对，按照上面的原则，则奇数个逆序对变为非逆序对，奇数个非逆序对变为逆序对，因此逆序对个数还是奇数。
- 若在交换的数中有偶数个逆序对，则由于 n-1 为偶数，因此剩下偶数个非逆序对，按照上面的原则，则偶数个逆序对变为非逆序对，偶数个非逆序对变为逆序对，因此逆序对个数还是偶数。

由此，就得出了结论：无论如何改变，展开后序列的逆序对数的奇偶性永远不变。

用归并排序求逆序对，再判定奇偶性是否相同即可。

AC-Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 500*500+100;
int temp[N];
ll msort(int l, int r, int *a) {
    if (l>=r) return 0;
    int mid = l+r>>1, k=0;
    ll res = msort(l, mid, a)+msort(mid+1, r, a);
    int i = l, j = mid+1;
    while (i<=mid && j<=r)
        if (a[i]<=a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++], res += (mid-i+1);
    while (i<=mid) temp[k++] = a[i++];
    while (j<=r) temp[k++] = a[j++];
    for (i=l, j=0; i<=r; i++, j++) a[i] = temp[j];
    return res;
}
int st[N], en[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL); 
    for (int n; cin >> n;) {
        n*=n;
        for(int i=1, x, f=0; i<=n&&cin>>x; i++, f|=(!x)) st[i-f] = x;
        for(int i=1, x, f=0; i<=n&&cin>>x; i++, f|=(!x)) en[i-f] = x;
        ll u = msort(1, n - 1, st);
        ll v = msort(1, n - 1, en);
        if((u&1)==(v&1)) cout << "TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}