poj1286

Description

Beads of red, blue or green colors are connected together into a circular necklace of n beads ( n < 24 ). If the repetitions that are produced by rotation around the center of the circular necklace or reflection to the axis of symmetry are all neglected, how many different forms of the necklace are there?

这里写图片描述
Input

The input has several lines, and each line contains the input data n.
-1 denotes the end of the input file.
Output

The output should contain the output data: Number of different forms, in each line correspondent to the input data.
Sample Input

4
5
-1
Sample Output

21
39
Source

Xi’an 2002
题意:给三种颜色的珠子串项链 允许翻转允许旋转且旋转或者翻转之后如果相同认为是一种方案
直接套用polya公式即可
首先考虑旋转操作 置换最多有n种否则就又变成原来的样子了 考虑其中旋转i个单位的循环节个数是多少
循环节长度又因为每个循环节都相同 所以个数就是
然后把lcm用gcd什么替换一下即可得到答案为gcd(i,n)
然后翻转的情况 针对n为奇数 考虑固定一个点为对称点那么(n-1)中都是循环节+1(自己也是循环节
n为偶数情况 考虑分割时候恰好切在两点上 循环节个数
或者恰好在两点之间循环节个数

 

分类: polya

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论