思路
polya定理/Burnside引理
本质不同的等价类数目就是把置换拆成循环,每个循环就是一个不动点,求所有置换方案的不动点数目的平均值
polya给出了求不动点数目的具体方法,循环中颜色相同,每个循环选什么颜色不冲突,选什么颜色都行,所以对应的方案数就是(n^L),L是循环的个数
polya定理的题目
考虑每种变换的方式,
如果旋转(k)个的话,相当于i和(i+k)%n在一个循环中,假设t的时候第一次完成了一次循环,所以(tk\% n = 0),所以(t=frac{n}{gcd(n,k)}),所以循环中有t个元素,一共(gcd(n,k))个循环
然后考虑对称的情况,如果是奇数个点就是点和相对的边,一共n种,每种有(frac{(n-1)}{2}+1)个循环
如果是偶数个点就是点和相对的点对称,一共(frac{n}{2})种,每种(frac{n-2}{2}+2)个循环
或者是边和相对的边对称,一个(frac{n}{2}),每种(frac{n}{2})个循环
Polya一般这样思考,面面对应旋转,点和对点对应旋转/对称,边中点和对边中点对应旋转/对称
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int pow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=(ans*a);
a=(a*a);
b>>=1;
}
return ans;
}
int gcd(int a,int b){
return (b==0)?a:gcd(b,a%b);
}
int n,ans=0;
signed main(){
while(scanf("%lld",&n)==1&&n!=-1){
if(n==0){
printf("0
");
continue;
}
ans=0;
int cnt=0;
for(int i=0;i<n;i++){
ans=(ans+pow(3,gcd(n,i)));
cnt++;
}
if(n%2){
ans=(ans+pow(3,(n-1)/2+1)*n);
cnt+=n;
}
else{
ans=(ans+pow(3,(n-2)/2+2)*(n/2));
cnt+=n/2;
ans=(ans+pow(3,n/2)*(n/2));
cnt+=n/2;
}
printf("%lld
",ans/cnt);
}
return 0;
}