POJ 1286

发表于 |

题目

$N$个珠子组成的圆环，用$3$种颜色去给珠子涂色，问有多少种不同的涂色方案。旋转或按对称轴反射之后相同的视作同一种方案。

数据范围

$0 \leq N \leq 23$

做法

Polya定理。找出珠子的所有置换。置换有2类，旋转和按对称轴反射。

  1. 旋转。旋转$k(0\leq k \leq N-1)$个珠子形成的置换写成不相杂轮换的乘积后，不相杂轮换的个数为$gcd(N,k)$个。
  2. 按对称轴反射。对$N$分奇偶讨论。$N$为奇数时，有$N$个置换，每个置换的不相杂轮换的个数是$1+\frac{N-1}{2}$。$N$为偶数时，有$\frac{N}{2}$个置换，每个置换的不相杂轮换个数为$1+\frac{N-2}{2}$；还有$\frac{N}{2}$个置换，每个置换的不相杂轮换个数为$2+\frac{N-2}{2}$。

由于$N$很小，不用任何优化，直接统计答案即可。

代码

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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
ll fastPow(ll a, int n)
{
  ll res = 1;
  for (; n; n >>= 1, a *= a) {
    if (n & 1) res *= a;
  }
  return res;
}
int main()
{
  while (scanf("%d", &N), N != -1) {
    if (N == 0) {
      printf("0\n");
      continue;
    }
    ll res = 0;
    for (int i = 0; i < N; ++i) {
      res += fastPow(3, __gcd(N, i));
    }
    if (N & 1) {
      res += N * fastPow(3, (N + 1) / 2);
    } else {
      res += N / 2 * (fastPow(3, N / 2) + fastPow(3, (N + 2) / 2));
    }
    res /= 2 * N;
    printf("%lld\n", res);
  }
  return 0;
}

总结

__gcd()函数在头文件algorithm中。