非常的喜欢这道题目!
首先还是老规矩,描述一下这道题目,题目是这个意思:项链和手镯,都是有若干个珠子串成的,不同之处在于项链不能够反转,而手镯可以反转,而给你n个珠子,t中颜色,每种颜色可以是任意多个珠子,问你,可以构造出多少种项链和手镯!
这道题目,我私自认为是一道关于置换方面的经典的例题!开始我都没沉下心来去考虑这个题目,觉得不好玩,但是,当我沉下心仔细去考虑这道题目的时候,我真的觉得数学博大精深!
首先,我们来看看两个很有用的关于置换的定理,第一个就是Burnside(烧边?)引理,描述为:对于置换f,一种着色方案s经过一种置换后不变,则成这种着色方案s是f的不动点。若将f的不动点计为C(f),则可以证明等价类数目为所有C(f)的平均值。
一般用这个引理就可以解决所有的问题了。
而Polya定理是这样给出的:如果置换f可以分解成m(f)个循环的乘积,那么每个循环内的颜色必须相同(必须的,不信则可以自己试验一下),假设有t中颜色,那么C(f)= t^(m(f)),则等价类数目也可求得、
而这个题目就是非常经典的置换的题目,只不过对于手镯来说,你就要注意手镯是可以旋转,也可以翻转的,所以最后是要加上旋转的数目,并且切记奇偶是不同的两种情况。
贴出代码:
#include <stdio.h> #include <string.h> #include <iostream> #include <string> using namespace std; typedef long long LL; const int MAXN = 55; LL pow_t[MAXN]; void init(int t) { pow_t[0] = 1; for (int i = 1; i < MAXN; i++) { pow_t[i] = pow_t[i - 1] * t; } } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int n, t; while (scanf("%d%d", &n, &t) != EOF) { init(t); LL ans1 = 0; for (int i = 0; i < n; i++) { ans1 += pow_t[gcd(i, n)]; } LL ans2 = 0; if (n % 2 == 0) { ans2 = n / 2 * (pow_t[(n + 2) / 2] + pow_t[n / 2]); } else { ans2 = n * pow_t[(n + 1) / 2]; } printf("%lld %lld\n", ans1 / n, (ans1 + ans2) / (2 * n)); } // system("pause"); return 0; }