奇数码问题
有一个\(n\times n\)的网格图，网格由\(0\sim n-1\)组成，现在你可以进行操作，每次操作选择0与其相邻的位置上的数交换位置，给出两个网格图的初始局面，询问这两个局面是否能够互相到达，\(n\in\text{奇数},1\leq n\leq 500\)。
解
此题套结论即可，但是不清楚结论，可以参考我的八数码的总结，但是我至今没有它的完整的证明，网上有一篇，但是我看不懂。
因为n是奇数，于是能够互相到达，当且仅当网格图拆行成列后形成的序列的不考虑0的逆序对个数奇偶性相同，注意这个结论\(n=1\)时候不成立，需要特判。
参考代码：
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define ll long long
using namespace std;
ll lxd(int,int,int[]);
int a[250050],b[250050],at,bt,te[250050];
int main(){int n;while(scanf("%d",&n)!=EOF){at^=at,bt^=bt;for(int i(1),j,k;i<=n;++i)for(j=1;j<=n;++j){scanf("%d",&k);if(k)a[++at]=k;}for(int i(1),j,k;i<=n;++i)for(j=1;j<=n;++j){scanf("%d",&k);if(k)b[++bt]=k;}if(n==1){puts(a[1]==b[1]?"TAK":"NIE");continue;}puts((lxd(1,at,a)&1)==(lxd(1,bt,b)&1)?"TAK":"NIE");}return 0;
}
ll lxd(int l,int r,int a[]){if(l==r)return 0;int mid(l+r>>1),i(l),j(mid+1),k(l);ll ans(lxd(l,mid,a)+lxd(j,r,a));while(i<=mid&&j<=r)if(a[i]<=a[j])te[k++]=a[i++];else te[k++]=a[j++],ans+=mid-i+1;while(i<=mid)te[k++]=a[i++];while(j<=r)te[k++]=a[j++];for(i=l;i<=r;++i)a[i]=te[i];return ans;
}