USACO All Latin Squares

这是一道相当令人不爽的一道题目。容易看出核心算法是DFS，可是，需要剪枝...

最直观的剪枝：
当前面N-1行都确定后，最后一行也就确定了，因此，可以直接回溯。
使用这个剪枝后，在N=6时耗时约0.9s，勉强通过。N=7时，用了20min也没有算出来。T_T

有一定技巧的剪枝：
以N=5为例，有下面一个解：

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

那么，如果我们把第2行和第4行交换，根据题义，得到的方形也是满足要求的。
因此，只要算出一种情况，然后把总数×(N-1)！就可以得出解了。
如何做到这种效果呢？
这里用到了一个方法——化无序为有序：把第一列强制设定为1、2、3、4、5，然后DFS即可。
当和第一个剪枝一起使用时，N=6时耗时接近0s，不过N=7依然要耗费约20s。需要进一步改进。

奇异的剪枝：
经本人尝试，可以在DFS前填充（2,2）位置的数字，第一次填1，做一遍DFS后改成3，根据两个数据就可以求出总数了。
这个剪枝可以把N=7的运行时间缩短到6s左右。

离奇的剪枝：
带有一点记忆化的思想，貌似和置换群有些关系，本人也是看了题解才知道的，详见代码了。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N;
int row[10],col[10];
int map[10];   //the second row
int t;
long long tmp_cnt;
long long cnt[10][10] = {};
long long ans = 0;
int cycle_cnt,cycle_product;
int idx;

void calc_idx()
{
   int l,k,j;
   static int v[10];
   cycle_cnt = 0;
   cycle_product = 1;
   memset(v,0,sizeof(v));
   for(k = 1;k <= N;k ++)
   {
       if(v[k])    continue;
       v[k] = 1;
       l = 1;
       for(j = map[k];j != k;j = map[j])
       {
           v[j] = 1;
           l ++;
       }
       cycle_cnt ++;
       cycle_product *= l;
   }
}

void dfs(int r,int c)
{
   if(r == N)
   {
       tmp_cnt ++;
       return;
   }
   int i;
   for(i = 1;i <= N;i ++)
   {
       if((((row[r] | col[c]) >> i) & 1) == 0)
       {
           row[r] |= (1 << i);
           col[c] |= (1 << i);
           if(c == N)
           {
               dfs(r + 1,2);
           }
           else
           {
               dfs(r,c + 1);
           }
           col[c] ^= (1 << i);
           row[r] ^= (1 << i);
       }
   }
}

void map_init()
{
   int i;
   for(i = 1;i <= N;i ++)
   {
       col[i] = 1 << i;
       row[i] = 1 << i;
   }
   col[1] = 0xFFFF;
   row[1] = 0xFFFF;
   map[1] = 2;
}

long long fac(int n)
{
   long long a = 1;
   while(n > 1)
   {
       a *= n;
       n --;
   }
   return a;
}

void pre(int k)
{
   int i;
   if(k == N + 1)
   {
       calc_idx();
       if(cnt[cycle_cnt][cycle_product] > 0)
       {
           ans += cnt[cycle_cnt][cycle_product];
       }
       else
       {
           tmp_cnt = 0;
           dfs(3,2);
           cnt[cycle_cnt][cycle_product] = tmp_cnt;
           ans += tmp_cnt;
       }
       return;
   }
   for(i = 1;i <= N;i ++)
   {
       if((((row[2] | col[k]) >> i) & 1) == 0)
       {
           row[2] |= (1 << i);
           col[k] |= (1 << i);
           map[k] = i;
           pre(k + 1);
           row[2] ^= (1 << i);
           col[k] ^= (1 << i);
       }
   }
}

int main()
{
   freopen("latin.in","r",stdin);
   freopen("latin.out","w",stdout);
   scanf("%d",&N);
   map_init();
   if(N >= 5)
   {
       pre(2);
       printf("%lld\n",ans * fac(N - 1));
   }
   else
   {
       tmp_cnt = 0;
       dfs(2,2);
       printf("%lld\n",tmp_cnt * fac(N - 1));
   }
   return 0;
}