首页 > 代码库 > POJ 2409 Let it Bead [置换群 Polya]
POJ 2409 Let it Bead [置换群 Polya]
传送门
题意：$m$种颜色$n$颗珠子，定义旋转和翻转两种置换，求不等价着色数
暴力求每个置换的循环节也许会$T?$
我们可以发现一些规律：
翻转：
$n$为奇数时每个置换有$1+\frac{n-1}{2}$个循环
$n$为偶数时穿过点的对称有$\frac{n}{2}$个循环，穿过边的有$\frac{n}{2}+1$个循环
旋转：
旋转$i$次的置换的循环个数为$gcd(n,i)$
可以这样想，从一个点开始每次走$i$步最后走到原位的最少步数$a$就是一个循环的长度
$ ai \equiv \pmod n$
$ i \mid ai,n \mid ai \rightarrow a=\frac{lcm(i,n)}{i}$
辣么$\frac{n}{a}=gcd(n,i)$就是循环个数啦
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=1005;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int m,n;inline int Pow(int a,int b){ int re=1; for(;b;b>>=1,a*=a) if(b&1) re*=a; return re;}inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int main(){ freopen("in","r",stdin); while(true){ m=read();n=read(); if(m==0&&n==0) break; int ans=0; for(int i=0;i<n;i++) ans+=Pow(m,gcd(n,i)); if(n&1) ans+=n*Pow(m,(n+1)>>1); else ans+=(n>>1)*Pow(m,n>>1)+(n>>1)*Pow(m,(n>>1)+1); ans/=n<<1; printf("%d\n",ans); }}
POJ 2409 Let it Bead [置换群 Polya]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。