polya定理

Pólya定理：用于解决等价类计数问题的，所谓等价类计数问题是指题目中会定义一种等价系，满足这个关系的元素都会被看成同一类，并只需要统计一次，最终需要统计所有的不同方案数。

我们可以分三步来解决这个问题。

1．确定置换群G。

2．计算每个置换的循环节个数。

3．代磨庆入公式：(其中，m为颜色的种数)

。

( 一）基于正方形的置换：

设边长为n的正方形，c种颜色。

旋转只有 0，90，180，270度三种旋法。

旋0度，则置换的轮换数为n n

旋90度，n为偶数时，则置换的轮换数为n n/4，n为奇数，则置换的轮换数为(n n-1)/4+1

旋180度，n为偶数时，则置换的轮换数为n n/2，n为奇数，则置换的轮换数为(n n-1)/2+1

旋270度，n为偶数时，则置换的轮换数为n n/4，n为奇数，则置换的轮换数为(n*n-1)/瞎闭握4+1

反射 沿对角反射两种，沿对边中点连线反射两种

n为偶态核数时，沿对边中点连线反射两种的置换轮换数为 n n/2

沿对角反射两种的置换轮换数为 (n n-n)/2+n

n为奇数时，沿对边中点连线反射两种的置换轮换数为 (n n-n)/2+n

沿对角反射两种的置换轮换数为 (n n-n)/2+n

https://vjudge.net/problem/HDU-1812

（高精度用java方便）

（二 ）基于环形的置换：

一个由n个点组成的环

旋转有n中置换：

对于每种置换轮换数为：gcd(n,i)

翻转（对称）：

奇数时只有n种相同的置换：

一个顶点和一条边的中点连线为轴（n个）：pow(c,n/2+1)

偶数时分成两大类置换：

1、边和边的中点连线为轴（n/2个)：pow(c,n/2+1)

2、点和点的连线为轴(n/2个)：pow(c,n/2)

参考博客

https://vjudge.net/problem/HDU-3923

这祥行个程序可行：

#include<stdio.h>

#include<stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -1

typedef int status

typedef int ElemType

typedef struct Polynode

{

ElemType coef

ElemType exp

struct Polynode *next

}PolyNode,*PolyList

void menu()

PolyList PolyCreate()

void PolyAdd(PolyList Polya,PolyList Polyb)

void PolySub(PolyList polya, PolyList polyb)

void PrintPoly(PolyList polya)

void menu()

{

printf("输入选择的功能\n"核拿)

printf("1,相加\n")

printf("2,相减\n")

}

PolyList PolyCreate()

{

PolyNode *head,*rear,*s

ElemType c,e

head=(PolyNode*)malloc(sizeof(PolyNode))

if(!head)exit(OVERFLOW)

rear=head

scanf("%d %d"谨氏哗,&c,&e)

while(c!=0)

{ s=(PolyNode*)malloc(sizeof(PolyNode))

s->coef=c

s->exp=e

rear->next=s

rear=s

scanf("%d %d",&c,&e)}

rear->next=NULL

return(head)}

void PolyAdd(PolyList polya, PolyList polyb)

{PolyNode *p, *q, *pre, *temp

ElemType sum

p=polya->next

q=polyb->next

pre=polya

while (p!=NULL &&q!=NULL){if(p->exp<q->exp)

{pre->next=ppre=pre->next

p=p->next}

else if ( p->exp==q->exp)

{ sum=p->coef + q->coef

if (sum!=0){ p->coef=sum

pre->next=p

pre=pre->nextp=p->next

temp=qq=q->nextfree(temp)}

else{ temp=p->nextfree(p)

p=temp temp=q->nextfree(q)

q=temp }

}

else{ pre->next=q

pre=pre->next

q =q->next}

}

if(p!=NULL)pre->next=p

else pre->next=q

}

void PrintPoly(PolyList polya)

{

PolyNode *p

p=polya->next

while(p)

{printf("%d ",p->coef)

printf("%d\t",p->exp)

p=p->next }

}

void PolySub(PolyList polya, PolyList polyb)

{

PolyNode *p, *q, *pre, *temp

ElemType sum

p=polya->next

q=polyb->next

pre=polya

while (p!=NULL &&q!=NULL)

{if(p->exp<q->exp){

pre->next=p

pre=pre->next

p=p->next

}

else if ( p->exp==q->exp)

{ sum=p->coef-q->coef

if (sum!=0)

{ p->coef=sum

pre->next=p

pre=pre->next

p=p->next

temp=qq=q->next

free(temp)}

else{

temp=p->nextfree(p)

p=temp

temp=q->next

free(q)

q=temp

}

}

else{ pre->next=q

pre=pre->next

q =q->next}

}

if(p!=NULL)pre->next=p

else pre->next=q

}

int main(void)

{ PolyNode *pa,*pb

int j

printf("输入多项式A B\n")

printf("输入方式为: coef1 exp11 coef2 exp2 0 0\n")

printf("最后用 0 0 结束\n")

printf("请输入多项式a\n")

pa=PolyCreate()

printf("请输入多项式b\n")

pb=PolyCreate()

menu()

scanf("%d",&j)

switch (j)

{

case 1:{PolyAdd(pa,pb)break}

case 2:{PolySub(pa,pb)break}

}

printf("输出结果为:\n")PrintPoly(pa)

system("PAUSE")

return 0

}

---