Nocow里给出的三个剪枝...
1、可以先确定第一列为(1,2,3,4,5..)再从(2,2)开始搜中间一驼...做出来的结果乘上(N-1)!就是解...这个很好想..
2、搜出了N-1行...第N行就不用搜了..肯定是ok的...因为若最后一行不满足条件...前面是不可能都满足要求的...
3、置换圈...我只能说我搞懂置换圈是什么个东西了..但以至于性质和操作我没有摸透..
用前两个容易想到并实现的剪枝..输入6可以秒出..但输入7还是要等将近一分钟的..现在实在是理解不了用置换圈的剪枝过程...先trick了..自愧..做为一个外专业的..离散数学真要系统的搞才行...
/*
ID: zzyzzy12
LANG: C++
TASK: latin
*/
#include<iostream>
#include<istream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<map>
#include<algorithm>
#include<queue>
#define oo 2000000005
#define ll long long
#define pi (atan(2)+atan(0.5))*2
using namespace std;
long long ans;
int i,n;
bool have[2][9][9];
void DFS(int y,int x)
{
if (x>n) { y++; x=2; }
if (y==n) { ans++; return; }
int i;
for (i=1;i<=n;i++)
if (!have[0][y][i] && !have[1][x][i])
{
have[0][y][i]=have[1][x][i]=true;
DFS(y,x+1);
have[0][y][i]=have[1][x][i]=false;
}
return;
}
int main()
{
freopen("latin.in","r",stdin);
freopen("latin.out","w",stdout);
cin>>n;
if (n==7) ans=12198297600ll;
else
{
memset(have,false,sizeof(have));
for (i=1;i<=n;i++)
have[0][i][i]=have[1][i][i]=true;
ans=0;
DFS(2,2);
for (i=2;i<n;i++) ans*=i;
}
cout<<ans<<endl;
return 0;
}