记录编号	82230	评测结果	AAAAAA
题目名称	拉丁正方形	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.214 s
提交时间	2013-11-22 17:59:13	内存使用	6.62 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
const ll SIZEN=8;
vector<pair<ll,ll> > scanlis;//按照何种顺序搜索
bool line[SIZEN][SIZEN]={0};//行信息,[i][j]=1表示第i行有j
bool row[SIZEN][SIZEN]={0};//列信息,意义类似
ll board[SIZEN][SIZEN]={0};
ll fact[]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
ll n;
ll sum;
ll cnt[1000000]={0};
void print(ll s[SIZEN][SIZEN]){//调试接口
	ll i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++) cout<<s[i][j]<<" ";
		cout<<endl;
	}
}
bool flag[SIZEN]={0};
ll getring(ll x){
	ll tot=0;
	ll now=x;
	do{
		tot++;
		flag[now]=true;
		now=board[2][now];
	}while(now!=x);
	return tot;
}
ll id=0;
bool legal(void){
	memset(flag,0,sizeof(flag));
	ll i;
	ll temp;
	id=0;
	for(i=1;i<=n;i++){
		if(!flag[i]){
			temp=getring(i);
			id=max(id,temp);
		}
	}
	if(cnt[id]){
		return false;
	}
	return true;
}
void fillblock(ll x,ll y,ll i){
	line[x][i]=true;
	row[y][i]=true;
	board[x][y]=i;
}
void eraseblock(ll x,ll y,ll i){
	board[x][y]=0;
	line[x][i]=false;
	row[y][i]=false;
}
void DFS(ll k){//现在需要确定scanlis中的第k个位置
	if(k==scanlis.size()){
		sum++;
		cnt[id]++;
		return;
	}
	ll i;
	ll x,y;//x行y列
	x=scanlis[k].first,y=scanlis[k].second;
	for(i=1;i<=n;i++){
		if(line[x][i]||row[y][i]) continue;
		if(x==2&&y==n){
			fillblock(x,y,i);
			if(legal()){
				DFS(k+1);
			}
			else sum+=cnt[id];
			eraseblock(x,y,i);
			return;
		}
		fillblock(x,y,i);
		DFS(k+1);
		eraseblock(x,y,i);
	}
}
void init(void){
	scanf("%lld",&n);
	ll i,j;
	for(i=2;i<n;i++){
		for(j=2;j<=n;j++) scanlis.push_back(make_pair(i,j));
	}
	for(i=1;i<=n;i++) fillblock(1,i,i);
	for(i=2;i<=n;i++) fillblock(i,1,i);
}
int main(){
	freopen("latinus.in","r",stdin);
	freopen("latinus.out","w",stdout);
	init();
	DFS(0);
	sum*=fact[n-1];
	cout<<sum<<endl;
	return 0;
}