随笔-141  评论-9  文章-3  trackbacks-0
预备知识:

对于一个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, 
falsesizeof(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
+12);
            }
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, 
truesizeof(row));
        memset(col, 
truesizeof(col));
        memset(cnt, 
0sizeof(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 小阮 阅读(1033) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理