置换与Polya 计数原理-应用部分

置换与Polya 计数原理-应用部分

// polya定理 求解循环节数const int N=1e3+10;int per[N];bool vis[N];int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}int polya(int n){ int pos,sum=0; memset(vis,0,sizeof(vis)); for(int i=0;i

有一个长度是n的环，

对于旋转，顺时针k或逆时针旋转n-k个单位，那么它对应的循环节的个数是gcd(k, n) （不断相减）, 长度是 n/gcd(k,n)

对于翻转，如果n是奇数，那么循环节数：

即（n+1)/2 个

如果是偶数，那么：

即 (n+2)/2

或者:

即 n/2

置换群的个数：2*n    （顺时针和逆时针）

给定m种颜色的柱子，每一种颜色的珠子的个数是无限的，将这些珠子组成长度为n的项链，问能做成多少种不同的项链？（经过旋转或翻转后得到的两条项链重合在一起对应的柱子的颜色相同算同一种项链）

input： m n

output: answer

#include #include #include #include using namespace std;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}int main(){ int m,n; while(cin>>m>>n){ int sum=0; for(int i=1;i<=n;i++){ sum+=(int)pow(m*1.0,gcd(i,n)*1.0); } if(n&1) sum+=(int)(n*pow(m*1.0,(n+1)/2.0)); else { sum+=(int)(n/2*pow(m*1.0,n/2.0)); sum+=(int)(n/2*pow(m*1.0,(n+2)/2.0)); } printf("%d\n",sum/2/n); } return 0;}

LK的项链

​​n（0<=n<=24）,请你帮她计算一下一共可以用这一盒珠子可以穿出多少条不同的项链。通过旋转、翻转达到同一种状态的被认为是相同的项 链。

#include #include #include #include using namespace std;typedef long long LL;LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}int main(){ int n; while(cin>>n){ if(n==-1) break; if(n==0) { puts("0"); continue; } LL sum=0; for(LL i=1;i<=n;i++){ sum+=(LL)pow(3.0,gcd(i,n)*1.0); } if(n&1) sum+=(LL)(n*pow(3.0,(n+1)/2.0)); else { sum+=(LL)(n/2*pow(3.0,n/2.0)); sum+=(LL)(n/2*pow(3.0,(n+2)/2.0)); } printf("%lld\n",sum/2/n); } return 0;}

POJ 3270 Cow Sorting

​​1 2 5 3

--3-->

4 2 1 5 3

--4-->

4 2 3 5 1

--6-->

4 2 3 1 5

--5-->

1 2 3 4 5

result=sum+(cnt-2)*min1

又如：

外面最小值：1

1  100 101 99

--100-->

99 100 101 1

--102-->

99 100   1   101

--101-->

99   1    100 101

--100-->

1  99   100 101

result=sum+(cnt+1) Min+min1.

啊，举例不当，上面的结果不如循环内直接交换，但是有这样的情况：

sum+(cnt+1) Min+min1 < sum+(cnt-2)*min1

(cnt+1)Min<(cnt-3)min1

#include #include #include #include using namespace std;typedef long long LL;const int N=1e4+5,M=1e5+10;struct node{ LL cnt; //循环节长度 LL min1; //循环内的最小值 LL all; //循环内元素的和}s[N];LL cow[N],ls[N];bool vis[M];void dfs(LL start,LL tot,LL n){ //映射关系 for(int i=0;i>n){ memset(vis,0,sizeof(vis)); for(int i=0;i

POJ 1286 Necklace of Beads

​​ 这题和nyist   280  LK的项链 几乎一样。 POJ 1721 CARDS​​​给出洗完牌后的顺序，求出原来的顺序

洗牌规则，例如：

3 2 4 5 1

---------

1 2 3 4 5

--变化后-->：

4 2 5 1 3

问题有点像同余里的逆元

举个例子，1->2->3->1   循环节长度是3，原数是1，那么经过8次变化后，答案是8%3后的变化结果，那么再经过3-2次变化就是原来的数字，所以求解原数就是新数变化 3-8%3次。即cir-s%cir

#include #include using namespace std;int c[1005][1005];int find(int dex,int n){ int *pr=c[dex-1],*now=c[dex]; bool ok=1; for(int i=1;i<=n;i++){ now[i]=pr[pr[i]]; if(now[i]!=c[0][i]) ok=0; } if(ok) return dex; else return find(dex+1,n);}int main(){ //freopen("cin.txt","r",stdin); int n,s; while(cin>>n>>s){ for(int i=1;i<=n;i++){ scanf("%d",&c[0][i]); } int cir=find(1,n); int dex=cir-s%cir; for(int i=1;i<=n;i++){ printf("%d\n",c[dex][i]); } } return 0;}

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