512009 - 黑白瓷砖

【题目描述】黑白瓷砖(ceramic)

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

有一天琪儿想试试看这些瓷砖究竟能漆成多少种本质不同的图案。所谓两种图案本质不同就是其中的一种图案无论如何旋转、或者翻转、或者同时旋转和翻转都不能得到另外一种图案。 如图12.15所示,旋转是将瓷砖三角形整体顺时针旋转120o或240o。 图12.15

如图12.16所示,翻转是将瓷砖三角形整体左右翻转180o。 图12.16

如图12.17所示,琪儿知道n=1时有两种不同的漆绘方案,n=2时也只有4种不同的漆绘方案。 图12.17

但是后来琪儿发现n在变大的过程中,漆绘方案增长的速度很快,在n=14的时候,居然有6760803201217259503457555972096种不同的漆绘方案。因此她决定请你编写程序帮他求解本质不同的漆绘方案数。

输入

一个正整数n(n≤20)。

输出

以一行的形式输出问题的解(解的位置不超过200位)。

样例

输入

1

输出

2

输入

2

输出

4
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题