POJ 1286 Necklace of Beads(Polya原理)

题目链接：
POJ 1286 Necklace of Beads
题意：
$有3种颜色来涂n颗珠子的项链，考虑翻转和旋转，问不同的项链个数?$
分析：
假设有$t$种颜色，$n$颗珠子。

• 旋转

如果逆时针旋转$i$颗珠子的间距，则珠子$0,i,2i,...$构成一个循环，这个循环有$\frac{i*n}{gcd(i,n}$个元素。根据对称性，所有循环的长度均相同，因此一共有$gcd(i,n)$个循环。这些置换的不动点总数为$a=\sum_{i=0}^{n-1}t^{gcd(i,n)}$

• 翻转

当$n$为奇数时，对称轴有$n$条，这条对称轴形成$\frac{n-1}{2}$个长度为$2$的循环和$1$个长度为$1$的循环，即$\frac{n+1}{2}$个循环。这些置换的不动点总数为$b=n*t^{\frac{n+1}{2}}$
当$n$为偶数时，对称轴分两种。穿过珠子的对称轴有$\frac{n}{2}$条，各形成$\frac{n}{2}-1$个长度为$2$的循环和$2$个长度为$1$的循环；不穿过珠子的对称轴有$\frac{n}{2}$条，各形成$\frac{n}{2}$个长度为$2$的循环。这些置换的不动点总数为$b=\frac{n}{2}(t^{\frac{n}{2}+1}+t^\frac{n}{2})$

根据$Polya$原理，当考虑旋转时的方案数为$\frac{a}{n}$,同时考虑旋转和翻转时的方案数为$\frac{a+b}{2n}$.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
const int MAX_N = 25;ll quick_pow(ll a, ll b)
{ll res = 1, tmp = a;while(b) {if(b & 1) res *= tmp;tmp *= tmp;b >>= 1;}return res;
}int gcd(int a, int b) 
{return b == 0 ? a : gcd(b, a % b);
}int main()
{int n;while(~scanf("%d", &n) && n != -1) {ll a = 0, b = 0;for(int i = 0; i < n; ++i ) {a += quick_pow(3, gcd(i, n));} if(n & 1) b = (ll)n * quick_pow(3, (n + 1) / 2);else b = (ll) n / 2 * (quick_pow(3, n / 2 + 1) + quick_pow(3, n / 2));if(n == 0) printf("0\n");else printf("%lld\n", (a + b) / 2 / n);}return 0;
}