All Latin Squares
A square arrangement of numbers
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
is a 5 x 5 Latin Square because each whole number from 1 to 5 appears once and only once in each row and column.
Write a program that will compute the number of NxN Latin Squares whose first row is:
1 2 3 4 5.......N
Your program should work for any N from 2 to 7.
PROGRAM NAME: latin
INPUT FORMAT
One line containing the integer N.
SAMPLE INPUT (file latin.in)
5
OUTPUT FORMAT
A single integer telling the number of latin squares whose first row is 1 2 3 . . . N.
SAMPLE OUTPUT (file latin.out)
1344 ————————————————————题解
第一行已经固定了，如果我们固定第一列为1 2 3 4 5……n 那么我们计算出的方案数乘以（n-1）！即可
然后这个优化加上位运算也只能过6。7就很尴尬了。
还有一个神一般的优化
例如
1 2 3 4 5
2 1 4 3 5
这其中有两个置换圈 1,2 和 3，4,5
如果再来一种搜索搜到了
1 2 3 4 5
2 3 1 5 4
这其中有两个置换圈 1 2 3 和 4 5
注意到了吗这个置换圈要先从大到小排序
这样的话其实这两种情况是等价的
为什么等价？
长度为2的两个圈 1 2 和 4 5可以分别一一对应
长度为3的两个圈3 4 5 和 1 2 3可以分别一一对应
也就是像我们手里得到了一张转换表，把第一种情况里的后四排的
1写成4
2写成5
3写成1
4写成2
5写成3
最后得到了一个新的拉丁方格
所以我们用一个哈希表记录置换圈的长度和所有置换圈长度的乘积，算过一遍的方案直接得出，节省很多时间……
orz反正我是想不到的
/*
LANG: C++
PROG: latin
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define siji(i,x,y) for(int i=(x); i<=(y) ; ++i)
#define ivorysi
#define o(x) ((x)*(x))
using namespace std;
typedef long long ll;
int n;
int col[],row[],num[][];
bool v[];
ll ans,h[][];//置换圈的长度乘积，个数
void init() {
scanf("%d",&n);
siji(i,,n) {
num[][i]=i;
num[i][]=i;
col[i]=(<<i);
row[i]=(<<i);
}
memset(h,-,sizeof(h));
} ll dfs(int x,int y) {
if(x>=n){
return ;
}
ll res=;
if(x==&&y==) {
memset(v,,sizeof(v));
int cnt=,len=;
siji(i,,n) {
if(v[i]) continue;
v[i]=;
int rec=;
for(int l=num[][i];l!=i;l=num[][l]) {
v[l]=;
++rec;
}
len*=rec;
++cnt;
}
if(h[len][cnt]!=-) return h[len][cnt];
siji(i,,n) {
if(((col[y]&(<<i))==) && ((row[x]&(<<i))==)) {
col[y]|=(<<i);
row[x]|=(<<i);
num[x][y]=i;
if(y==n) res+=dfs(x+,);
else res+=dfs(x,y+);
col[y]^=(<<i);
row[x]^=(<<i);
num[x][y]=;
}
}
return h[len][cnt]=res;
}
siji(i,,n) {
if(((col[y]&(<<i))==) && ((row[x]&(<<i))==)) {
col[y]|=(<<i);
row[x]|=(<<i);
num[x][y]=i;
if(y==n) res+=dfs(x+,);
else res+=dfs(x,y+);
col[y]^=(<<i);
row[x]^=(<<i);
num[x][y]=;
}
}
return res;
}
void solve() {
init();
//if(n==7) {cout<<"12198297600"<<endl;return;}
ans=dfs(,);
siji(i,,n-) ans*=i;
printf("%lld\n",ans);
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("latin.in","r",stdin);
freopen("latin.out","w",stdout);
#else
freopen("f1.in","r",stdin);
//freopen("f1.out","w",stdout);
#endif
solve();
return ;
}