- 把(frac{n(n+1)}2)个正六边形摆成一个“三角形”，然后给每个六边形染上颜色。
- 有顺时针/逆时针旋转(120^circ)和左右翻转两种操作，问有多少种本质不同的染色方案。
- (nle20)
(Polya)定理
考虑(Polya)定理的公式：
[L=frac1{|G|}sum_{i=1}^sm^{c(g_i)}
]
方便起见令(m=frac {n(n+1)}2)，然后就是对几种置换方式分类讨论。
原排列： 显然(c(g)=m)。
一次翻转： 对称轴上的点就是单独一个置换环，两旁的点则都有对应点合成一个置换环，因此 (c(g)=sum_{i=1}^nlceilfrac i2 ceil)。
一次旋转： 当(n\%3=1)时有个中心点，(c(g)=frac{m-1}3+1)；当(n\%3 ot=1)的时候没有中心，(c(g)=frac m3)。（显然，顺时针和逆时针旋转是一样的）
翻转+旋转： 稍微有点麻烦，最好还是自己画下图理解一下。当(n\%3=1)时，中心单独一个，一个端点单独一个，剩余的点与对面两两合成一个置换环，(c(g)=frac{m-2}2+2)；当(n\%3 ot=1)时，依然对称轴上的点单独一个，两旁的点都有对应点，(c(g)=sum_{i=1}^nlceilfrac i2 ceil)。
代码：(O(n))
n=int(input())
m=n*(n+1)//2#总六边形个数
t=2**m#原排列
c=0
for i in range(1,n+1):
c+=(i+1)//2#计算每行置换环数
t+=2**c#一次翻转
if n%3==1:#根据有无中心分类讨论
t+=2*((2**((m-1)//3+1))+(2**((m-4)//2+3)))#一次旋转；翻转+旋转
else:#没有中心
t+=2*((2**(m//3))+(2**c))#一次旋转；翻转+旋转
print(t//6)#除以群大小