POJ2409 Let it Bead——Polya

POJ2409 Let it Bead——Polya

题意：

给你n个珠子，每个珠子有m种染色方法，将这些珠子做成长度为n的项链，问有多少种方法。两种方法是相同的当且仅当两种项链可以通过旋转或者翻转变成一种项链

思路：

题中有两种置换方式：

1.旋转置换。分别顺时针旋转 i 个珠子，其循环节长度为 GCD(i，n)。（0

2.翻转置换。根据 N 的奇偶性分情况讨论。

N为奇数时：

以第 i 个珠子为顶点和中心翻转，翻转后，第 i 个珠子保持不变，其余珠子两两相

互对换，因为有 N 个珠子，所以有 N 种翻转置换，每种翻转循环节数为 (N+1) / 2。

N为偶数时，有两种翻转方式：

以两边相对的两个珠子为轴和中心翻转，翻转后，这两个珠子保持不变，其余珠子

两两相互对换，共有 N/2 种翻转置换，每种翻转循环节数为 (N+2) / 2。

以相邻的珠子中间连线为轴和中心翻转，翻转后，所有珠子两两相互对换，共有 N/2

种翻转置换，每种翻转循环节数为 N/2。

#include #include #include #include using namespace std;int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b));}int ipow(int x, int a) { int ans = 1; while (a) { if (a & 1) ans *= x; x *= x; a >>= 1; } return ans;}int main() { int m, n; while (~scanf("%d %d", &m, &n) && m + n) { int ans = 0; for (int i = 0; i < n; i++) ans += ipow(m, gcd(i, n)); if (n & 1) ans += n * ipow(m, (n+1)/2); else { ans += n/2 * ipow(m, (n+2)/2); ans += n/2 * ipow(m, n/2); } ans /= (2*n); printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。