POJ 1286 Necklace of Beads

灰太狼 2021-12-23 13:59 143阅读 0赞

### 思路 ###

**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\n"); 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\n",ans/cnt); } return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10589563.html