奇数码游戏两个局面可达，当且仅当两个局面下网格中的数依次写成1行nn-1个元素的序列后(不考虑空格)，逆序对个数的奇偶性相同。 例如题目描述中的第一个局面写成[52813467]。 该结论的必要性很容易证明:空格左右移动时，写成的序列显然不变;空格向上(下)移动时， 相当于某个数与它后(前)边的n-1个数交换了位置，因为n-1是偶数，所以逆序对数的变化也只能是偶数。 该结论的充分性证明较为复杂，我们将不在此大篇幅讨论这样一个数学问题。 上面的结论还可以扩展到n为偶数的情况，此时两个局面可达，当且仅当两个局面对应网格写成序列后， “逆序对个数+两个局面下空格之间的行数之差”的奇偶性相同。 事实上，在nm网格上(nm≥2)也服从上述两个结论之一(根据列数奇偶性分情况讨论)。 总而言之，n*m数码问题的有解性判定，可以转化为归并排序求逆序对来解决。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[310000], alen, tmp[310000]; LL ans;
void msort(int l, int r)
{
	if(l >= r) return ;
	int mid = (l + r) / 2;
	msort(l, mid); msort(mid + 1, r);
	int len = l, i = l, j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(a[i] > a[j])
		{
			ans += (mid - i + 1);
			tmp[len++] = a[j++];
		}
		else tmp[len++] = a[i++];
	}
	while(i <= mid) tmp[len++] = a[i++];
	while(j <= r) tmp[len++] = a[j++];
	for(int i = l; i <= r; i++) a[i] = tmp[i];
}
int main()
{
	int n;
	while(scanf("%d", &n) != EOF)
	{
		LL fa, fb;
		alen = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {scanf("%d", &a[++alen]); if(a[alen] == 0) alen--;}
		if(alen == 0) fa = 0; else {ans = 0; msort(1, alen); fa = ans;}
		alen = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {scanf("%d", &a[++alen]); if(a[alen] == 0) alen--;}
		if(alen == 0) fb = 0; else {ans = 0; msort(1, alen); fb = ans;}
		if( ((fa ^ fb) & 1) == 0 ) printf("TAK\n"); else printf("NIE\n");
	}
	return 0;
}

/*
奇数码游戏两个局面可达，当且仅当两个局面下网格中的数依次写成1行n*n-1个元素的序列后(不考虑空格)，
逆序对个数的奇偶性相同。
例如题目描述中的第一个局面写成[52813467]。
该结论的必要性很容易证明:空格左右移动时，写成的序列显然不变;空格向上(下)移动时，
相当于某个数与它后(前)边的n-1个数交换了位置，因为n-1是偶数，所以逆序对数的变化也只能是偶数。
该结论的充分性证明较为复杂，我们将不在此大篇幅讨论这样一个数学问题。
上面的结论还可以扩展到n为偶数的情况，此时两个局面可达，当且仅当两个局面对应网格写成序列后，
“逆序对个数+两个局面下空格之间的行数之差”的奇偶性相同。
事实上，在n*m网格上(nm≥2)也服从上述两个结论之一(根据列数奇偶性分情况讨论)。
总而言之，n*m数码问题的有解性判定，可以转化为归并排序求逆序对来解决。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[310000],alen,tmp[310000];LL ans;
void msort(int l,int r)
{
	if(l>=r) return ;
	int mid=(l+r)/2;
	msort(l,mid);msort(mid+1,r);
	int len=l,i=l,j=mid+1;
	while(i<=mid && j<=r)
	{
		if(a[i]>a[j])
		{
			ans+=(mid-i+1);
			tmp[len++]=a[j++];
		}
		else tmp[len++]=a[i++];
	}
	while(i<=mid) tmp[len++]=a[i++];
	while(j<=r) tmp[len++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		LL fa,fb;
		alen=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) {scanf("%d",&a[++alen]);if(a[alen]==0)alen--;}
		if(alen==0)fa=0;else {ans=0;msort(1,alen);fa=ans;}
		alen=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) {scanf("%d",&a[++alen]);if(a[alen]==0)alen--;}
		if(alen==0)fb=0;else {ans=0;msort(1,alen);fb=ans;}
		if( ((fa ^ fb)&1)  ==0 ) printf("TAK\n");else printf("NIE\n");
	}
	return 0;
}

<br />

<br />

<br />

<br />