相信很多初學者剛接觸Polya定理的時候一臉懵逼，因為它以許多離散數學的知識為基礎，所以不太好上手，所以我在這里把模板貼出來。

Polya定理是用來求出m種顏色涂入n個對象一共有多少種方法的一種定理。

暴力版模板

#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long LL; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } LL polya(int m,int n) //m color ,n number { LL tot=0; //方案數 for(int i=1;i<=n;i++) tot+=pow(m,gcd(n,i)); tot/=n; if(n%2!=0) tot+=pow(m,(n+1)/2); //odd else tot+=(pow(m,n/2)+pow(m,n/2+1))/2; return tot/2; }

還有一種歐拉函數優化版

時間復雜度是O(sqrt(n))

#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long LL; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int euler_phi(int n) { int res=1; for(int i=2;i*i<=n;i++) if(n%i==0) { //說明i|n n/=i,res*=i-1; while(n%i==0) n/=i,res*=i; //說明i^2|n } if(n>1) res*=n-1; return res; } LL polya(int m,int n) //m color ,n number { LL tot=0; //方案數 for(int i=1;i*i<=n;i++) //1~sqrt(n) { if(n%i) continue; //當i不是n的約數時就進入下一次循環 tot+=euler_phi(i)*pow(m,n/i); //d=gcd(n,i) d為n的因數，且有euler_phi(n/i)個 if(i*i!=n) tot+=euler_phi(n/i)*pow(m,i); //當i*i==n時，不必算兩次 } tot/=n; if(n%2!=0) tot+=pow(m,(n+1)/2); //odd else tot+=(pow(m,n/2)+pow(m,n/2+1))/2; return tot/2; }

總結

以上是生活随笔為你收集整理的Polya定理模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。