左右交换不说了,下面考虑上下交换
对于每次交换,会发生:
$+x$对逆序对
$-y$对逆序对
又因为:
$x+y=n-1,n-1$为偶数
所以$x,y$奇偶性相同,$x-y=偶数$
即对于每次交换,逆序对奇偶性不变
所以只需判断两个矩阵转换后的序列是否相同即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
typedef long long ll;
using namespace std;
const int N=250010;
int n,x,cnt,a[N],c[N];
ll res1,res2;
inline int lowbit(int x){return x&(-x);}
void update(int x,int k){for(;x<=n*n;c[x]+=k,x+=lowbit(x));}
int query(int x){int s=0;for(;x;s+=c[x],x-=lowbit(x));return s;}
ll calc()
{
ll ret=0;
memset(c,0,sizeof(c)); cnt=0;
for(ri i=1;i<=n;i++)
for(ri j=1;j<=n;j++)
{
scanf("%d",&x);
if(x) a[++cnt]=x;
}
if(n==1) return 0;
for(ri i=n*n-1;i>=1;i--)
ret+=query(a[i]-1),update(a[i],1);
return ret;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
res1=calc(),res2=calc();
if((res1^res2)&1) printf("NIE\n");
else printf("TAK\n");
}
return 0;
}