程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 題目1286 Necklace of Beads(Polya定理)

POJ 題目1286 Necklace of Beads(Polya定理)

編輯:關於C++
Necklace of Beads Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 7061   Accepted: 2942

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

 

題目大意:

n個珠子串成一個圓,用三種顏色去塗色。問一共有多少種不同的塗色方法。

不同的塗色方法被定義為:如果這種塗色情況翻轉,旋轉不與其他情況相同就為不同。

 

解題思路:

Polya定理模版題。

對於順時針長度為i的旋轉,為pow(3,__gcd(n,i);

對於翻轉,當為奇數時,有:n*pow(3.0,n/2+1);

當為偶數時,有:n/2*pow(3.0,n/2)+n/2*pow(3.0,n/2+1);

 

一共有2*n種情況,最後要除以2*n


ac代碼

 

#include
#include
#include
int gcd(int a,int b)
{
	if(a

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved