自动搬运

查看原文

来自洛谷，原作者为

	Drifty zzzzzzᙆᙆᙆᙆᙆᙆ

搬运于2025-08-24 22:58:05，当前版本为作者最后更新于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;
}