usaco training 5.4.1 All Latin Squares 題解

【原題】

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
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4
      

是一個5×5的拉丁幻方，即每個1到5的整數在每行每列都出現且出現一次。 斜體文字 寫個程式計算N×N的的拉丁幻方的總數且要求第一行是：

1 2 3 4 5.......N
      

2<=N<=7

[編輯]格式

PROGRAM NAME: latin

INPUT FORMAT

一行包含一個整數N

OUTPUT FORMAT

隻有一行，表示拉丁正方形的個數，且拉丁正方形的第一行為 1 2 3 . . . N.

[編輯]SAMPLE INPUT (file latin.in)

5
      

[編輯]SAMPLE OUTPUT (file latin.out)

1344      

【初步分析】明顯就是搜尋題。做過了那道The prime的題目，我對這種隻要求橫行和豎行不重複、且N<=7的題目非常的不屑。因為沒有明顯的搜尋順序，我直接按順序搜尋。

【小優化】當然，其實最後一行和最後一列都可以不搜。

【結果】前6個點秒過，第7個點即使開100s也過不去！隻好厚着臉皮去網上看題解：其實答案的範圍超過了int類型！這也太坑了吧！即使對于每一個解，使用O(1)的效率，也是A不過去的！匆匆看題解，有一個剪枝非常的快——我們強制把第一列搞成遞增（1，2，3，。。n）最後再把解乘上(n-1)!

【後記】N<=7，明顯是打表的節奏。加了優化後，我也要23s過，是以無奈隻好打表了。

【代碼】

/*
PROG:latin
ID:juan1973
LANG:C++
*/
#include<stdio.h>
using namespace std;
const int maxn=10;
int a[maxn][maxn],n,i;
long long ans;
bool lie[maxn][maxn],hang[maxn][maxn];
void count(int x,int y)
{
  if (y>n) 
  {
    x++;y=2;
  }
  int i;
  if (x>=n) 
  {
    int j,k;
    for (i=2;i<=n;i++)
    {
      for (j=1;j<=n;j++)
        if (!lie[i][j]) {k=j;break;}
      if (hang[n][k]) return;hang[n][k]=true;
    }
    ans++;
    for (i=1;i<=n;i++) hang[n][i]=false;
    return;
  }
  for (i=1;i<=n;i++)
    if (!lie[y][i]&&!hang[x][i])
    {
      a[x][y]=i;
      lie[y][i]=true;hang[x][i]=true;
      count(x,y+1);
      lie[y][i]=false;hang[x][i]=false;
    }
}
int main()
{
  freopen("latin.in","r",stdin);
  freopen("latin.out","w",stdout);
  scanf("%ld",&n);
  if (n==7) {printf("12198297600\n");return 0;}
  for (i=1;i<=n;i++)
  {
    a[1][i]=i;
    lie[i][i]=true;
    a[i][1]=i;
    hang[i][i]=true;
  }
  count(2,2);
  for (i=n-1;i>1;i--) ans*=(long long) (i);
  printf("%lld\n",ans);
  return 0;
}