CC

自然万物都趋向从有序变得无序

0%

Necklace of Beads POJ - 1286 polya定理

发表于 更新于 分类于 Valine：

题目链接

题目

这里写图片描述

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

题意:

用三种颜色组成一个具有n个珠子的手串,问有多少种不同的方式.

思路:

题目有两种转置方式:

一:选择置换:
这里写图片描述

二,翻转置换:
翻转置换: 假设 n 为奇数, 那么$m^ { \frac {n}{2}+1}∗n 种.如果n为偶数,那么此时有两种翻转,一种是以两个点对称,另一种是以两条边对称,那么有种. 如果n为偶数,那么此时有两种翻转, 一种是以两个点对称, 另一种是以两条边对称 , 那么有m^{\frac {n}{2}+1}∗ \frac {n}{2}+m^{ \frac {n}{2}}∗\frac {n}{2}$ 种.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

typedef long long LL;
const int maxn = 10000;
bool ispri[maxn];
int pri[maxn];
int num;

void isprime(){
    num = 0;
    memset(ispri, false,sizeof(ispri));
    for(int i = 2; i < maxn; ++i){
        if(!ispri[i]) pri[++num] = i;
        for(int j = 1; j <= num && i * pri[j] < maxn; ++j){
            ispri[i * pri[j]] = true;
            if (i % pri[j] == 0)break;
        }
    }
}

int euler(int n){
    int ans = n;
    for(int  i = 1;i <= num && pri[i] * pri[i] <= n; ++i)
    if ( n % pri[i] == 0){
        ans -= ans / pri[i];
        while(n % pri[i] == 0) n /= pri[i];
    }
    if(n > 1) ans -= ans / n;
    return ans;
}

LL qpow(LL x, LL n){
    LL ans = 1;
    while(n){
        if (n&1) ans *= x;
        x *= x;
        n >>= 1;
    }return ans;
}

int main(){
    int n;
    isprime();
    ios::sync_with_stdio(false);
    while(cin >> n && n != -1){
        LL ans = 0;
        if(n){
        for(int i = 1; i * i <= n; ++i){
            if(n % i == 0)
                if(i * i == n)
                    ans += euler(i) * qpow(3, n / i);
                else ans += euler(i) * qpow(3, n / i) + euler(n / i) * qpow(3, i);
        }if (n&1)
            ans += n * qpow(3, n / 2 + 1);
        else ans += ( qpow(3, n / 2) + qpow(3, n / 2 + 1 )) * ( n / 2);
        ans /= 2 * n;
        }cout<<ans<<endl;
    }return 0;
}