Necklace of Beads

第一题Polya计数，好有意思的定理。

题目输入很简单，就是一个n，问n个在环上等距放置的球，可以用3种颜色染色，用各种方式（旋转/翻转）去除重复染色方案后，输出总染色方案数。

看完Polya定理后，结合题目条件想了一下便推出了解：

若另某个位置为0，顺时针方向依次为位置0、1、……、n-1，那么，可以分别另0号球于0、1、……、n-1开始，沿顺时/逆时针方向依次摆下其余编号的球，那么总共有2n种不同的置换方案的，这也是覆盖了全部置换的情况。接下来便是对每种置换方案计算各自的轮换数了，这步也很简单的，对每个不在自己位置且未标记的球迭代求对应的轮换，每次找到新的轮换都将对应方案的轮换数增一即可。最后sum(pow(3,ci))/2n便是结果了。

本来以为可以1A的。。。结果没考虑n=0的情况。。。还是太嫩了。。。

但即使AC了也只是略微明白定理如何使用，证明看了一下发现不太好懂，就暂时放下了。