波利亚计数（群论）

大家好，欢迎来到IT知识分享网。

目录

一，波利亚计数

二，OJ实战

POJ 1286 Necklace of Beads

POJ 2409 Let it Bead

POJ 2154 Color

一，波利亚计数

对于一般的情况：

其中phi是欧拉函数

对于一般的情况：

其中phi是欧拉函数

二，OJ实战

POJ 1286 Necklace of Beads

题目：

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? 

公式：

代码：

#include <iostream> using namespace std; int phi(int n) { int r = n; for (int i = 2; i*i <= n; i++) { if (n%i == 0) { while (n%i == 0)n /= i; r = r / i*(i - 1); } } if (n > 1)r = r / n*(n - 1); return r; } long long mi(int a, int m) { if (m == 0)return 1; long long b = mi(a, m / 2); b = b*b; if (m % 2)b *= a; return b; } int main() { int n; while (cin >> n) { if (n < 0)break; if (n == 0) { cout << 0 << endl; continue; } long long ans = 0, i = 0; while (++i*i < n) { if (n%i)continue; ans += phi(n / i)*mi(3, i) + phi(i) *mi(3, n / i); } if (i*i == n)ans += phi(i)*mi(3, i); ans /= n; ans += (mi(3, (n + 1) / 2) + mi(3, n / 2 + 1)) / 2; cout << ans / 2 << endl; } return 0; }

16ms AC

根据这个代码，还可以二次编码成更快的代码：

#include <iostream> using namespace std; int main() { int n,l[24] = { 0, 3, 6, 10, 21, 39, 92, 198, 498, 1219, 3210, 8418, 22913, 62415, , , , , , , , , ,  }; while (cin >> n)if (n < 0)break; else cout << l[n] << endl; return 0; }

POJ 2409 Let it Bead

题目：

Description

“Let it Bead” company is located upstairs at 700 Cannery Row in Monterey, CA. As you can deduce from the company name, their business is beads. Their PR department found out that customers are interested in buying colored bracelets. However, over 90 percent of the target audience insists that the bracelets be unique. (Just imagine what happened if two women showed up at the same party wearing identical bracelets!) It’s a good thing that bracelets can have different lengths and need not be made of beads of one color. Help the boss estimating maximum profit by calculating how many different bracelets can be produced. 

所以那个代码只需要改一点点就得到本题的代码：

#include <iostream> using namespace std; int phi(int n) { int r = n; for (int i = 2; i*i <= n; i++) { if (n%i == 0) { while (n%i == 0)n /= i; r = r / i*(i - 1); } } if (n > 1)r = r / n*(n - 1); return r; } long long mi(int a, int m) { if (m == 0)return 1; long long b = mi(a, m / 2); b = b*b; if (m % 2)b *= a; return b; } int main() { int m, n; while (cin >> m >> n) { if (n == 0)break; long long ans = 0, i = 0; while (++i*i < n) { if (n%i)continue; ans += phi(n / i)*mi(m, i) + phi(i) *mi(m, n / i); } if (i*i == n)ans += phi(i)*mi(m, i); ans /= n; ans += (mi(m, (n + 1) / 2) + mi(m, n / 2 + 1)) / 2; cout << ans / 2 << endl; } return 0; }

POJ 2154 Color

题目：

Description

Beads of N colors are connected together into a circular necklace of N beads (N<=). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected. 

在计算这个式子mod p的时候，因为有除n这个运算，这是无法用同余解决的，

除非确定n和p互质，可以找逆元

本题采用的是另外一种方法，直接取定m就是n

那么上式化为

代码：

#include <iostream> using namespace std; int phi(int n) { int r = n; for (int i = 2; i*i <= n; i++) { if (n%i == 0) { while (n%i == 0)n /= i; r = r / i*(i - 1); } } if (n > 1)r = r / n*(n - 1); return r; } int mi(int a, int m, int p) { if (m == 0)return 1; int b = mi(a, m / 2, p); b = b*b%p; if (m % 2)b *= a; return b%p; } int main() { int t, n, p, ans; cin >> t; while (t--) { cin >> n >> p; ans = 0; int i = 0; while (++i*i < n) { if (n%i)continue; ans += phi(n / i) % p*mi(n%p, i - 1, p) % p + phi(i) % p*mi(n%p, n / i - 1, p) % p; } if (i*i == n)ans += phi(i) % p*mi(n%p, i - 1, p) % p; cout << ans%p << endl; } return 0; }

如果对称也算一种的话，就变成了另外一个题目：POJ 1286 Necklace of Beads