題目：Color

?

題意：將正n邊形的n個頂點用n種顏色染色，問有多少種方案（答案mod p，且可由旋轉(zhuǎn)互相得到的算一種）

?

先說說Pólya定理

設(shè)Q是n個對象的一個置換群，用m種顏色涂染這n個對象，一個對象涂任意一種顏色，則在Q作用下不等價的方案數(shù)為:???

|Q|為置換群中置換的個數(shù)，為將置換q表示成不相雜的輪換的個數(shù)，其中包括單輪換，m為顏色數(shù)。

?

分析可以知道本題方案的表達式為：

然后就直接代碼了：

#include <stdio.h> #include <string.h> #define N 36000int p;int pr[N]; bool prime[N]; int k=0;void isprime() {int i,j;memset(prime,true,sizeof(prime));for(i=2;i<N;i++){if(prime[i]){pr[k++]=i;for(j=i+i;j<N;j+=i){prime[j]=false;}}} }int phi(int n) {int rea=n,i;for(i=0;pr[i]*pr[i]<=n;i++){if(n%pr[i]==0){rea=rea-rea/pr[i];while(n%pr[i]==0) n/=pr[i];}}if(n>1)rea=rea-rea/n;return rea%p; }int quick_mod(int a,int b) {int ans=1;a%=p;while(b){if(b&1){ans=ans*a%p;b--;}b>>=1;a=a*a%p;}return ans; }int main() {int i,t,n,ans;isprime();scanf("%d",&t);while(t--){ans=0;scanf("%d%d",&n,&p);for(i=1;i*i<=n;i++){if(i*i==n)ans=(ans+quick_mod(n,i-1)*phi(i))%p;else if(n%i==0)ans=(ans+quick_mod(n,i-1)*phi(n/i)+quick_mod(n,n/i-1)*phi(i))%p;}printf("%d\n",ans%p);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ2154(Pólya定理与欧拉函数优化)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。