OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【AHOI2002】黑白瓷砖

【题目描述】

小可可在课余的时候受美术老师的委派从事一项漆绘瓷砖的任务。首先把n(n+1)/2块正六边形瓷砖拼成三角形的形状,右图给出了n=3时拼成的“瓷砖三角形”。然后把每一块瓷砖漆成纯白色或者纯黑色,而且每块瓷砖的正、反两面都必须漆成同样的颜色。 

有一天小可可突发奇想,觉得有必要试试看这些瓷砖究竟能够漆成多少种本质不同的图案。所谓两种图案本质不同就是其中的一种图案无论如何旋转、或者翻转、或者同时旋转和翻转都不能得到另外一种图案。

旋转是将瓷砖三角形整体顺时针旋转120度或240度。

翻转是将瓷砖三角形整体左右翻动180度。


一开始,小可可觉得这项实验很有意思,他知道n=2时有两个本质不同的漆绘方案,n=4时也只有四个本质不同的漆绘方案。小可可还把这些漆绘方案画了出来。

 但是后来小可可发现在变大的过程中,漆绘方案的数目增长很快,在n=14的时候,居然有6760803201217259503457555972096种不同的漆绘方案。这果然是一项非常艰巨的实验。因此他决定请你编写程序帮他求解本质不同的漆绘方案数。



【输入】

一个正整数n, n≤20。

【输出】

一行正整数,代表问题的解s。

【输入样例】

14

【输出样例】

6760803201217259503457555972096

【数据范围】

s不超过200位

【题解】

Pólya定理/置换群第一题,撒花~

这是一道经典的置换群问题,不过原来的三种操作不足以构成群,因此要增加三种操作,即单位元和两个斜着的翻转。

计算循环节比较简单,脑补一下就出来了。单位元的循环节个数就是瓷砖数,旋转是瓷砖数/3向上取整,翻转是(瓷砖数+n/2向上取整)/2,然后Pólya定理计算即可。

记得高精度~

【代码】

我在认真思考做笔记的事……

http://paste.ubuntu.com/9912148/

评论

© OI技术宅 | Powered by LOFTER