USACO/latin

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .5中的OI题目All Latin Squares的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

这题开始我的搜索TLE.。然后就去想怎么构造……最后发现纯属浪费时间。 这题似乎没有什么规律可循。只能搜索。 朴素搜索只能过6个点(5个点啊【2-6】)，7就TLE了。

经过测试发现,在n=7时,经过剪枝共有12198297600个解.如果将DFS改成枚举,再修炼一下代码能力,应该不会TLE的.

---

优化技巧

1. 只需要搜边长n-1的正方形即可。在第一行的排列已经确定以后，第1列的每一种排列对应的方案数都相同。所以只需要搜索(2,2)开始的边长为n-1的正方形即可。
2. 搜到第4行就不用搜了，第五行已经确定了。
3. 超级优化 (by Maigo）：用到一点置换的知识。对于相邻的两行，搜索出来后可以得到几个置换圈，把这些圈的个数从小到大排序后记录下来。那么对于两种方案，如果圈的个数相同且对应圈的大小相同，那么这两种方案本质上是相同的。可以用一个hash记录。记录的时候把所有置换圈的长度相乘，那么对于个数相同的方案肯定不会冲突（谁让n这么小……）。（这样貌似不对，因为对于置换圈(2,2,2)和(4,2)算出来的记录是一样的，但它们的方案数貌似不一样。） ——orz Maigo 好像是有问题，但是你可以把置换圈长度序列当(n+1)进制算，也就8^7种（而且明显到不了上限8^7） ----某路人 （没问题这里说的是个数相同的方案，(2,2,2)和(4,2)显然个数不同——路人戊）

路人甲

关于置换圈的问题想了很久，果然思维还是不行啊，估计过几天又得忘了，这里写一下我的思路，给菜鸟们看吧

为什么说如果两个方案圈的个数相同且对应圈的大小相同，那么这两种方案本质上是相同的呢？

看下面的数列

1 2 3 4 5

2 1 4 5 3 （1）

置换圈为（1，2），（3，4，5）照以上的说法，它与下面的置换应该是等价的：

1 2 3 4 5

2 3 1 5 4 （2）

置换为（1，2，3），（4，5）

怎么看出是等价的呢，把（2）中（1，2，3）->（3，4，5），（4，5）->（1，2），进行这样的变换，再把第一行排下序，我们就会发现两种排列产生的latin方是等价的。

那么如果圈不一样呢,

1 2 3 4

2 1 4 3

1 2 3 4

2 3 1 4

就会发现（1）方案根本没办法通过变换的方式转化为（2）方案，就是说一个长度为3的圈经过变换之后，长度还是为3，如果两个变换长度根本不匹配，那么就是不等价的。

路人乙

一个比较有效（个人认为）的优化： 由于一个可行解交换其中两行后仍然是可行解，所以搜索时规定每一行的1～N的排列的序号要比上一行的大，最后将结果乘上（N-1）！（第一行不算）

由于每一行第一个元素各不相同，所以要保证每一行的1～N的排列的序号要比上一行的大，第I行的第一各元素一定为I

---

萧兵乙：您这不就是对优化技巧1的解释吗…… 路人乙：Sorry，我当时没看懂优化技巧1……

游客N

位运算，请联想N皇后=_,-

参考代码

C

C++

Pascal