POJ2154(Pólya定理与欧拉函数优化)

不错的Polya题目&＃xff0c;有两篇博客给了两个不同的思路&＃xff0c;但最终公式都相同代码也相同

题意&＃xff1a;给出两个整数n和p&＃xff0c;代表n个珠子&＃xff0c;n种颜色&＃xff0c;要求不同的项链数&＃xff0c;翻转置换不考虑。结果模p.

题解&＃xff1a;

基本知识&＃xff1a;共有n种置换&＃xff08;都是旋转置换&＃xff09;&＃xff0c;每种置换循环节的个数为gcd(n , i) , 对应循环节长度为L&＃61;n / gcd(n , i)&＃xff08;旋转置换中的所有循环节的长度相同&＃xff09;其中i为转的位置数。 
普通求法: ∑n^( gcd(n,i) ) 0<&＃61;i

我们知道gcd&＃xff08;i,n)表示了循环节的个数。例如gcd(2,6) &＃61; 2, 它的具体过程为&＃xff1a;[1&＃xff0c;3&＃xff0c;5] [2&＃xff0c;4&＃xff0c;6]

对于任意一个循环置换&＃xff0c;他所有循环节的长度为 n / gcd(i,n)&＃xff0c;在上面的例子中: 循环节长度 &＃61; 6 / gcd(2,6) &＃61; 3

为了方便说明&＃xff0c;用L表示循环节的长度&＃xff0c;显然 L | n

如果我们枚举L&＃xff0c;求出对于每一个L有多少个i, 使得 L &＃61; n / gcd (i,n)&＃xff0c; 那么我们实际上也得到了循环节个数为 n / L 的置换个数。

将L &＃61; n / gcd (i,n)转换一下得到&＃xff1a;n / L &＃61; gcd&＃xff08;i,n )

设 cnt &＃xff1d; n / L &＃61; gcd(i, n)  注&＃xff1a;cnt表示循环节个数&＃xff0c;L表示每一个循环节的长度

因为 cnt | i, 所以可令 i &＃xff1d; cnt * t; ( 因为0 <&＃61; i

又因为 cnt &＃61; n / L&＃xff0c; 所以 n &＃61; cnt * L;

则 gcd ( i, n ) &＃61; gcd ( cnt*t, cnt*L ) &＃61; cnt;  ①

可知当 gcd ( t, L ) &＃61; 1 时 ① 式成立。

由于 gcd ( t, L ) &＃61; 1 的个数就是 Euler(L)的个数&＃xff0c;

所以我们可以得到结论&＃xff1a;循环节个数为n/L的置换有Euler(L)个。&＃xff08;因为满足条件的i的个数就是t的个数也就是Euler(L) &＃xff09;

总结起来如下&＃xff1a;

为了求 ∑n^( gcd(n,i) ) 0<&＃61;i

下面解法更简洁易懂&＃xff1a;

题意&＃xff1a;将正n边形的n个顶点用n种颜色染色&＃xff0c;问有多少种方案&＃xff08;答案mod p&＃xff0c;且可由旋转互相得到的算一种&＃xff09;

先说说Pólya定理

设Q是n个对象的一个置换群&＃xff0c;用m种颜色涂染这n个对象&＃xff0c;一个对象涂任意一种颜色&＃xff0c;则在Q作用下不等价的方案数为:   

|Q|为置换群中置换的个数&＃xff0c;为将置换q表示成不相杂的轮换的个数&＃xff0c;其中包括单轮换&＃xff0c;m为颜色数。

分析可以知道本题方案的表达式为&＃xff1a;

代码&＃xff1a;

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

参考&＃xff1a;

POJ 2154 Color polya计算&＃43;欧拉优化

POJ2154(Pólya定理与欧拉函数优化)

POJ 2154 Color Polya定理&＃43;欧拉函数