108.奇数码
结论：n为奇数，左右交换不改变逆序对数个数，上下交换不改变逆序对奇偶性
因为上下交换相当改变了n-1个数和一个数的相对位置，即本来（n-1）个数中与那一个数形成逆序对的变成非逆序对，非逆序对变成逆序对。总共有n-1对（偶数对）。

1.若有奇数个逆序对，则有奇数个非逆序对。
改变位置后，按上述规则，还是奇数个逆序对。

2.若有偶数个逆序对，则有偶数个非逆序对。
改变位置后，按上述规则，还是偶数个逆序对。

奇数+奇数 = 偶数
偶数+偶数 = 偶数

#include<cstdio>
#include<algorithm>
int a[250010],b[250010],brr[250010];
using namespace std;
int merge(int *a,int l,int r)
{
    if(r-l < 1)
        return 0;
    int ans = 0;
    int mid = (l+r)>>1;
    ans+=merge(a,l,mid);
    ans+=merge(a,mid+1,r);

    int i = l,j = mid+1;
    int k = l;
    while(i <= mid&&j <= r)//比较哪个区域的数小，放进辅助数组
    {

        if(a[i]<=a[j])
        {

            brr[k++] = a[i++];
        }
        else{
            ans += mid-i+1;///ans+=mid-i+1同理，j包括j后所有数都可以和a[i]组成逆序对
            brr[k++] = a[j++];
        }
    }
    ///那个区域剩下数，放进辅助数组
    while(i <= mid) brr[k++] = a[i++];
    while(j <= r) brr[k++] = a[j++];
    ///放回原数组的原l,r区域内
    for(int i = l;i <= r;i++)
        a[i] = brr[i];

    return ans;
}
int main()
{
    int n,x;
    while(scanf("%d",&n)!=EOF)
    {
        int j = 1;
        for(int i = 1;i <= n*n;i++)
        {
            scanf("%d",&x);
            if(x)
            a[j++] = x;
        }
        /*for(int i = 1;i <= n*n-1;i++ )
        printf("%d ",a[i]);
        printf("\n");
        */
        j = 1;
        for(int i = 1;i <= n*n;i++)
        {
            scanf("%d",&x);
            if(x)
            b[j++] = x;
        }
        int a_sum = merge(a,1,n*n-1);
        int b_sum = merge(b,1,n*n-1);
        //printf("#%d %d\n",a_sum,b_sum);
        if((a_sum&1 ) == (b_sum&1) )
            printf("TAK\n");
        else
            printf("NIE\n");
    }

    return 0;

}