polya的精髓就在与对循环节的寻找，其中常遇到的问题就是项链染色类问题。
当项链旋转时有n种置换，循环节的个数分别是gcd(n, i);
当项链翻转时有n种置换,其中当项链珠子数位奇数时，循环节的个数是n/2+1
当项链珠子数是偶数个时,当翻转线穿过珠子时，循环节个数为n/2+1,否则为n/2;
1.poj 1286:
题目大意：用三种颜色对珠子数不超过24的项链染色，问有多少种染色情况。
这道题是最基本的polya定理考察，只要带入公式即可
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const long long maxa = ;
long long edge[maxa];
void rotate(long long n, long long ii){
for(long long i = ; i < n; i++){
edge[(i+ii)%n] = i;
}
}
void turn(long long n, long long ii){
for(long long i = n-, j= ; i >= ; i--, j++){
edge[(j+ ii)%n] = i;
}
}
long long vis[maxa];
void dfs(long long i){
if(vis[i] == )return ;
vis[i] = ;
dfs(edge[i]);
}
int main(){
int n, m;
while(scanf("%d%d", &m, &n), n+m){
if(n == ){
printf("0\n");
continue;
}
long long ans = ;
for(long long i = ; i < n; i++){
rotate(n, i);
long long o = ;
memset(vis, , sizeof(vis));
for(long long k = ;k < n; k++){
if(vis[k]==){
o ++;
dfs(k);
}
}
long long sum = ;
for(long long k = ;k < o; k++){
sum *= m;
}
ans += sum;
}
for(long long i = ; i < n; i++){
turn(n, i);
long long o = ;
memset(vis, , sizeof(vis));
for(long long k = ;k < n; k++){
if(vis[k]==){
o ++;
dfs(k);
}
}
long long sum = ;
for(long long k = ;k < o; k++){
sum *= m;
}
ans += sum;
}
cout<<ans/n/<<endl;
}
}
2.poj 2409
题目大意，用c种颜色染n个珠子组成的项链，也是最基本的polya定理考察
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const long long maxa = ;
long long edge[maxa];
void rotate(long long n, long long ii){
for(long long i = ; i < n; i++){
edge[(i+ii)%n] = i;
}
}
void turn(long long n, long long ii){
for(long long i = n-, j= ; i >= ; i--, j++){
edge[(j+ ii)%n] = i;
}
}
long long vis[maxa];
void dfs(long long i){
if(vis[i] == )return ;
vis[i] = ;
dfs(edge[i]);
}
int main(){
int n, m;
while(scanf("%d%d", &m, &n), n+m){
if(n == ){
printf("0\n");
continue;
}
long long ans = ;
for(long long i = ; i < n; i++){
rotate(n, i);
long long o = ;
memset(vis, , sizeof(vis));
for(long long k = ;k < n; k++){
if(vis[k]==){
o ++;
dfs(k);
}
}
long long sum = ;
for(long long k = ;k < o; k++){
sum *= m;
}
ans += sum;
}
for(long long i = ; i < n; i++){
turn(n, i);
long long o = ;
memset(vis, , sizeof(vis));
for(long long k = ;k < n; k++){
if(vis[k]==){
o ++;
dfs(k);
}
}
long long sum = ;
for(long long k = ;k < o; k++){
sum *= m;
}
ans += sum;
}
cout<<ans/n/<<endl;
}
}
3.hdu 1812
题目大意，用c种颜色对n*n的棋盘染色，有多少种方法
其实这道题就是可以看成一些(n+1)/2串项链，有八种置换，但是最坑的是大数怎么写都超时....万进制优化也超时.....打表还不让大那么大，java是很好的解决方法...谁爱写谁写....反正我不写啦啦啦啦
4.poj 2154
题目大意，用n种颜色染长度是n的项链，结果mod p n<=10^9,p<= 30000,这里的项链只考虑旋转。
常规解法是这样sum（n^gcd（n,i)）%q,但是数据太大了不允许，我们知道的是n的因子数是可以通过搜索求出来的，那么如果gcd(n,i) == m，则i的数量显然是euler(i)，需要注意的是最后除n的时候，n和p不一定互质所以需要在之前做处理，也就是将公式变成了sum（n^gcd（n,i)-1）%q，需要注意的是开long long会超时，所以在要用int，有些部分需要用同余模定理优化。
#include<iostream>
#include<string.h>
#include<cmath>
#include<stdio.h>
using namespace std;
const int maxa = ;
int app[maxa][];
int o;
int ans;
int n, q;
int m;
int euler(int n){ //返回euler(n)
//if(n == 1)return 0;
int res=n,a=n;
for(int i=;i*i<=a;i++){
if(a%i==){
res=res/i*(i-);//先进行除法是为了防止中间数据的溢出
while(a%i==) a/=i;
}
}
if(a>) res=res/a*(a-);
return res;
}
int kuick(int a, int b){
int aa = ;
if(b == )return ;
aa = kuick(a, b/);
aa *= aa;
aa%= q;
if(b &) aa*= a;
aa %= q;
return aa;
}
void dfs(int ii, int nn){//cout<<"*"<<ii<<" "<<o<<" "<<nn<<endl;
if(ii == o){
int aa = euler(n/nn) % q;
ans += aa * kuick(n%q, nn-);
ans %= q;
return;
}
dfs(ii+, nn);
int ss = ;
for(int i = ; i < app[ii][]; i++){
ss *= app[ii][];
dfs(ii+, ss*nn);
}
}
int main(){
cin>>m;
while(m--){
cin>>n>>q;
int N = n;
ans = ;
int sq = sqrt(n);
o = ;
for(int i = ;i <= sq; i++){
if(n % i == ){
app[o][] = i;
app[o][] = ;
while(n %i ==){
app[o][]++;
n /= i;
}
o++;
}
}
//printf("*");
if(n != ){
app[o][] = n;
app[o++][] = ;
}
n = N;
dfs(, );
cout<<ans<<endl;
}
}