Usaco Training Section 6.5 All Latin Squares

All Latin Squares 拉丁正方形
一种正方形的数字编排
1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4
是一个5*5 的拉丁正方形,每个1 到5 的整数在每行每列都出现且出现一次.
写个程序计算N*N 的的拉丁正方形的总数且要求第一行是:
1 2 3 4 5.......N
你的程序应该算称呼任意的从2 到7 的N(Your program should work for any N from 2 to 7)
PROGRAM NAME: latin
INPUT FORMAT
一行包含一个整数N
SAMPLE INPUT (file latin.in)
5
OUTPUT FORMAT
只有一行没,表示拉丁正方形的个数,且拉丁正方形的第一行为 1 2 3 . . . N.
SAMPLE OUTPUT (file latin.out)
1344

分析：这题……n<=7……打表可海星啊……

貌似n并不大，于是我们爆搜……然后T……

看来还是要优化的。有个容易想的优化：只搜1~n-1行

还有2个优化：

1. 将第一列填1~n，总数*(n-1)!
2. 置换群优化：求第二行的置换圈的最长长度，若搜完前两行时，两种情况中第二行的置换圈的最长长度相同，它们等价。其中置换圈就是将i和a[2][i]建无向边后得到的环，它的长度也就是换的大小。这个其实也很好理解，考虑第二行：1 2 5 3 4 和第二行：2 1 4 5 3，那么前者的1/2/3/4/5列等价于后者的2/1/4/5/3列。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline int read(){
	register int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}

const int fact[]={1,1,2,6,24,120,720};
int n,a[8],squn,cnt[8];
ll ans;
bool visx[8][8],visy[8][8],vis[8];

inline int qun(){
	for(register int i=1;i<=n;++i) vis[i]=0;
	register int x=2;
	for(register int i=1;i<=n;++i){
		if(vis[i]) continue;
		register int u=i,t=0;
		do{
			vis[u]=1;
			u=a[u];
			++t;
		}while(!vis[u]);
		if(t>x) x=t;
	}
	return x;
}

inline void dfs(int x,int y){
	for(register int i=1;i<=n;++i){
		if(!visx[i][x]&&!visy[i][y]){
			if(x==2){
				a[y]=i;
				if(y==n){
					squn=qun();
					if(cnt[squn]>0){
						ans+=cnt[squn];
						return;
					}
				}
			}
			visx[i][x]=1,visy[i][y]=1;
			if(y<n) dfs(x,y+1);
			else{
				if(x<n-1) dfs(x+1,2);
				else ++ans,++cnt[squn];
			}
			visx[i][x]=0,visy[i][y]=0;
		}
	}
}

int main()
{
	freopen("latin.in","r",stdin);
	freopen("latin.out","w",stdout);
	n=read();
	for(register int i=1;i<=n;++i) visy[i][i]=1;
	for(register int i=2;i<n;++i) visx[i][i]=1;
	a[1]=2;
	dfs(2,2);
	printf("%lld\n",ans*fact[n-1]);
	return 0;
}