Blackops

初心易得，始终难守

0%

POJ 1286 Necklace of Beads（Polya入门）

发表于 更新于 分类于 ， ，

Necklace of Beads
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10622 Accepted: 4293
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

题目链接：POJ 1286

题意就一串长为$n$的珠子可以翻转、旋转，每个珠子可以染$3$种颜色，求本质不同的染色方案数。
如果用burnside引理，则会有$3^n$次方种染色方案（标号数），非常麻烦。
而用Polya定理：

其中$m$为染色种数，$|G|$为置换操作个数。$c(p_i)$为某一置换$p_i$中循环的个数。用这个定理就大大缩小了标号数，答案非常好统计。

具体做法：将每个珠子都编号$1…n$，旋转和翻转看成对珠子编号的置换，由于题目中珠子是圆形的，那么可以有旋转和按照一个对称轴翻转两种情况。

  1. 旋转可以是$0$、每次转$1/n*360$度，每个置换内循环个数为$gcd(i,n)$，共$n$个置换
  2. 翻转分为奇数和偶数两种情况
    1. 奇数情况每个点和对边中点连线作为作为翻转轴，每个置换均有$(n - 1)/2+1$个循环，共$n$个这样的置换；
    2. 偶数情况每个对边中点连线作为翻转轴，均有$n/2$个循环，有$n/2$个这样的置换；对点两两一组，均有$(n-2)/2+2$个循环，有$n/2$个这样的置换。

所以置换群$G$的总数一定为$2n$，代码中写的麻烦一点是为了方便展示$G$的来源。
代码：

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;

ll qpow(ll a, ll b)
{
    ll r = 1;
    while (b)
    {
        if(b & 1)
            r *= a;
        a *= a;
        b >>= 1;
    }
    return r;
}
int main(void)
{
    ll n;
    while (cin >> n && ~n)
    {
        if(n == 0)
            puts("0");
        else
        {
            ll ans = 0;
            ll G = 0;
            for (ll cc = 0; cc < n; ++cc)///旋转的情况
            {
                ll cc_n = __gcd(n, cc);
                ans += qpow(3ll, cc_n);
                ++G;
            }
            ///翻转的情况
            if(n & 1) ///奇数每个点和对边作为中心，(n - 1)/2 +1个环，共n个中心
            {
                ans += n * (qpow(3ll, (n - 1ll) / 2ll  + 1ll));
                G += n;
            }
            else///偶数情况每个对边一组，n/2个环，有n/2组；对点一组，(n-2)/2+2个环，有n/2组
            {
                ans += (n >> 1) * qpow(3ll, ((n - 2ll) / 2ll + 2ll));
                G += (n >> 1);
                ans += (n >> 1) * (qpow(3ll, n >> 1));
                G += (n >> 1);
            }
            cout << ans / G << endl;
        }
    }
    return 0;
}