POJ 1286 Necklace of Beads （Polya定理）

POJ 1286 Necklace of Beads （Polya定理）

题目链接： ​​​POJ 1286​​

题意：就是求这样的三种颜色的组合有多少种？旋转和对称的重复的不算。

题解：Polya定理题。主要考虑旋转和对称的情况。

旋转：

当n=4时，可顺时针旋转0、1、2、3格 0格：（1）（2）（3）（4）可以互相转化 1格：（1,2,3,4）可以互相转化 2格：（1,3）（2,4）可以互相转化 3格：（1,2,3,4）可以互相转化 所以，ans=(34+31+32+31)4=24

旋转：顺时针旋转i格的置换中，循环的个数为gcd（i，n），每个循环的长度为n/gcd(i,n)

同理，当n=5时，ans=(35+31+31+31+31)5=51。

对称：

当n=4时，有4条对称轴 其中2条，（1,2）（3,4）可以互相转化 另外2条，（1）（3）（2,4）可以互相转化 ans=(2∗32+2∗33)4=18 当n=5时，有5条对称轴 每一条，（1）（2,5）（3,4） ans=(5∗33)5=27 以此类推。 最终ans=（旋转+对称）2。 所以就可以写代码了。

代码：

//#include #include #include #include using namespace std;typedef long long ll;ll q_pow(ll a,ll b){ ll ans =1; while(b) { if(b&1){ ans=(ans*a); } b>>=1; a=a*a; } return ans;}ll n;ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}int main(){ while(~scanf("%lld",&n)) { if(n==-1)break; if(n==0){ puts("0");continue; } ll ans = 0; if(n&1) { ans += q_pow(3,n/2+1)*n; } else { ans +=q_pow(3,n/2+1)*(n/2) + q_pow(3,n/2)*(n/2); } for(int i=1;i<=n;i++) { ans +=q_pow(3,gcd(i,n)); } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。