记录编号	194583	评测结果	AAAAAA
题目名称	拉丁正方形	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.255 s
提交时间	2015-10-16 20:09:59	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=10;
int N,H[SIZEN]={0},L[SIZEN]={0},tot=0;
int b[SIZEN]={0};
long long ans=0;
long long cnt[SIZEN]={0};
bool flag[SIZEN]={0};
int len=0;//置换群的长度,因为n很小，我们可以认为长度相同的两个置换群是相同的
class miku
{
	public:
	int x,y;
}P[100];
int get(int x,int i)
{
	return (x>>i)&1;
}
int change(int x,int j,int t)
{
	int tem=x>>j;
	x-=tem<<j;tem>>=1;x+=tem<<(j+1);x+=t<<j;
	return x;
}
void check(int x)
{
	for(int i=0;i<N;i++) cout<<get(x,i)<<" ";
	cout<<endl;
}
int get_len(int p)
{
	int tot=0;
	int now=p;
	do
	{
		tot++;
		flag[now]=1;
		//cout<<now<<" "<<p<<endl;
		now=b[now];
	}while(now!=p);
	return tot;
}
bool legal()
{
	int tem=0;
	len=0;
	memset(flag,0,sizeof(flag));
	for(int i=1;i<=N;i++)
	{
		if(!flag[i])
		{
			tem=get_len(i);
			len=max(len,tem);
		}
	}
	if(cnt[len]) return 0;
	else return 1;
}
void dfs(int x)
{
	if(x>tot-N+1) 
	{
		ans++;
		cnt[len]++;
		return;
	}
	miku v=P[x];
	//cout<<x<<endl;
	//check(H[P[x].x]);
	//check(L[P[x].y]);
	int m=H[v.x]|L[v.y];
	for(int i=1;i<=N;i++)
	{
		int p=get(m,i-1);
		if(p) continue;
		if(v.x==2) b[v.y]=i;
		if(v.x==2&&v.y==N)//超级优化----置换群
		{
			H[v.x]=change(H[v.x],i-1,1);
		    L[v.y]=change(L[v.y],i-1,1);
			if(legal())//判断当前置换群
				dfs(x+1);
			else ans+=cnt[len];
			H[v.x]=change(H[v.x],i-1,0);
		    L[v.y]=change(L[v.y],i-1,0);
			if(v.x==2) b[v.y]=0;
			return;
		}
		H[v.x]=change(H[v.x],i-1,1);
		L[v.y]=change(L[v.y],i-1,1);
		dfs(x+1);
		H[v.x]=change(H[v.x],i-1,0);
		L[v.y]=change(L[v.y],i-1,0);
		if(v.x==2) b[v.y]=0;
	}
}
int main()
{
	freopen("latinus.in","r",stdin);
	freopen("latinus.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++) L[i]=change(L[i],i-1,1);
	for(int i=2;i<=N;i++) H[i]=change(H[i],i-1,1);
	b[1]=2;
	for(int i=2;i<=N;i++) for(int j=2;j<=N;j++) P[++tot].x=i,P[tot].y=j;
	dfs(1);
	for(int i=1;i<N;i++) ans*=i;
	printf("%lld",ans);
	return 0;
}