预备知识：
对于一个n*n的拉丁方总数为N(k)。
当第一行为 1，2，……，n；第一列为1，2，……，n时， 拉丁方数为L(K)
存在如下公式：
N(K) = L(K) * N! * (N-1)!
说明：当L(k)确定后，第2到第你行的排列组成复合题意的拉丁方，所以乘以(n-1)!，第一到第N列的排列又是拉丁方，所以乘以 n!.
言归正传， 本题是第一行固定为1，2，……，n，第一列为1，2，……，n。所以求得L(K)乘以(n-1)!即可。
优化一：
置换群(by Maigo). 以5为例，
1 2 3 4 5
2 1 4 5 3 置换圈(1,2) , (3,4,5) 最长长度为3
和
1 2 3 4 5
2 3 1 5 4 置换圈(4,5), (1,2,3) 最长长度为3
他们是等价的，只是数字先后顺序有变化，他们产生的结果是一致（要多多思考）。
参考 cmykrgb1 ，利用最长长度作为索引进行hash，即枚举到第二行最后一列后，计算置换圈的最长长度，若已计算出这个长度的拉丁方总数，则返回该长度的所有可能数。
优化二：都可以想到，枚举到第n-1行即可， 直接ans++。
/**//*
ID: lorelei3
TASK: latin
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int fact[] = 
{1,1,2,6,24,120,720};
const int MAXN = 10;
ifstream fin("latin.in");
ofstream fout("latin.out");
int n, id, cnt[MAXN], a[MAXN];
long long ans;
bool row[MAXN][MAXN], col[MAXN][MAXN], v[MAXN];
void find(){
id=2;
int l,t;
memset(v, false, sizeof(v));
for(int i=1; i<=n; ++i)
if(!v[i]){
t=i; l=0;
do{
v[t]=true;
t = a[t];
l++;
}while(!v[t]);
if(l>id)
id=l;
}
}
void dfs(int x, int y){
for(int i=1; i<=n; ++i)
if(row[x][i] && col[y][i]){
if(x==2){
a[y]=i;
if(y==n){
find();
if(cnt[id]>0){
ans += cnt[id];
return;
}
}
}
row[x][i]=false;
col[y][i]=false;
if(y==n){
if(x==n-1){
cnt[id]++;
ans++;
}else
dfs(x+1, 2);
}else
dfs(x, y+1);
row[x][i]=true;
col[y][i]=true;
}
}
int main(){
fin>>n;
if(n==2)
ans=1;
else{
int i;
memset(row, true, sizeof(row));
memset(col, true, sizeof(col));
memset(cnt, 0, sizeof(cnt));
for(i=2; i<n; ++i) row[i][i]=false;
for(i=1; i<=n; ++i) col[i][i]=false;
ans=0;
a[1]=2;
dfs(2,2);
ans *= fact[n-1];
}
fout<<ans<<endl;
return 0;
}posted on 2011-02-14 15:09
小阮 阅读(1040)
评论(0) 编辑 收藏 引用 所属分类:
USACO