【题意简述】

　　用块完全一样的六边形瓷砖可以拼成一个边长为N的三角形图案（所谓"边长为N"，是指这个三角形的外圈每边有N块瓷砖），如图，就是一个边长为3的图案。

　　　　　　　　　
　　现在对此图案染色，图案中的每块瓷砖染成黑色或是白色。问题是求出边长为N的图案共有多少种本质不同的染色方案。两种染色后的图案，如果其中一种可以通过有限次的旋转（顺时针旋转120度或240度）、翻转（以从上到下的中线为对称轴左右交换）得到另外一种相同的图案，则认为它们的染色方案是本质相同的，否则认为是本质不同的。

　　在这个问题中，N<=20，并且保证解的长度不超过200。
【初步分析】

　　如果不考虑"本质不同"，则边长为N的图案共有种不同的染色方案，因为每块瓷砖有黑、白2种染色方法，每个图案中共有块瓷砖，根据乘法原理，不同的染色方案数就是。

　　然而本题棘手之处在于，要求的是"本质不同"的染色方案数，表面上不同的一组染色方案可能经过一定的旋转、翻转成为相同的，因此，它们只能作为一个本质不同方案进行计数。

　　首先明确一个简单而重要的问题：每个边长大于1的染色方案可以通过有限次旋转、翻转产生六种本质相同的方案，而且仅有这六种，分别是：本身、旋转120度、旋转240度、本身翻转、旋转120度后翻转、旋转240度后翻转。换句话说，每组本质相同的染色方案恰好有6个元素。

　　一个简单的想法是，对于染色方案规定某种"序"，也就是定义某种对染色方案进行"大小"比较的函数（自然，这个函数怎样定义是不确定的，但它必须对应于一种定义在染色方案集合上的偏序关系，也就是说，必须能够"比"出不同的染色方案的大小来），习惯上我们这样定义比较函数：规定黑色大于白色，然后从上到下，从左到右，以类似于字典排序的方法比较两种染色方案。形式化地规定了染色方案的"大小顺序"之后，我们就可以做到对每一组本质相同的染色方案只计数一次了，思想是：用每组中"最小"的一个方案作为此组的代表。

　　方法为：用递归（深度搜索）枚举每块瓷砖染黑色还是白色，对于最终枚举出的每个染色方案，比较它和它通过旋转、翻转产生的另外5种本质相同的方案，看这个方案是否是一组中"最小"的，如果是，则将总数加1。

　　然而，这种方法有很大的缺点：速度太慢。递归枚举所有瓷砖颜色的时间复杂度为O()，为指数级的非有效算法，当N取最大值20时，形式上复杂度高达的天文数字，更不要说最内层还要嵌套一定复杂度的旋转、翻转、比较操作。所以，这个算法是无法在时限内出解的。

　　注意，题目仅要我们求方案数，然而我们实际上产生了所有的方案！这，就是这种方法低效的原因！
【数学方法】

　　我们把问题抽象成数学模型，把图案上的个瓷砖从上到下，从左到右地编号为1至。进行一定的旋转、翻转后，某些瓷砖转移到了原来另外一些瓷砖的位置上，也就是说，从上到下，从左到右的位置上的瓷砖的编号不再是1至，而是另外的一串数。把这串数看成一个"置换"，那么一个原始的图案可以产生六种置换，构成一个"置换群"。现在对这个"置换群"进行2染色，根据Polya定理，对一个有g个元素的置换群用m种颜色染色的本质不同的染色方案数为
　　　　　　　　　　　
其中pi为第i个置换，c()为求置换的循环节数的函数。

　　对于此题，m恒等于2，当N>1时，g恒等于6，关键在于求出每一个置换的循环节数。这个问题比较简单，只需用一个二维数组记录图案的每个位置上的瓷砖编号，旋转、翻转操作就非常容易实现，通过此二维数组也很容易求得对应的置换，根据置换就可以求得循环节数，代入公式后就能算出结果了。当然，还需要高精度加法、求幂（不妨用反复平方法）、除法（最终要除以6，好在是高精度除以一个普通数）

　　需要注意的是，N=1对这种方法来说是特殊情况，因为一块瓷砖无法产生6个不同的置换，只有一个。可以特殊判断当N=1时直接输出2即可。
【总结】

　　这是本次省赛中较难的一题，因为它对选手数学方面的要求比较高，如果缺乏这方面的知识，就很难做好这题。可见，"数学是信息学之母"，培养数学能力，掌握数学知识是非常重要的。
【程序】

　　见ahoi02-9.pas。
【参考书籍】

　　《组合数学（第２版）》，卢开澄著，清华大学出版社。