题意

给你一个长为$n$的项链和手镯,每个珠子有$m$种颜色.

两个手镯定义为相同,即它们通过翻转和旋转得到一样的手镯.

两个项链定义为相同,即它们只能通过旋转得到一样的项链.

求出有多少种本质不同的项链和手镯.

$(1 \le n \le 50, 1 \le m \le 10)$

题解

大白书上的原题,一个裸的Polya定理(逃

Polya定理 : $$L=\frac{1}{|G|}\sum \limits _{i=1} ^{|G|} m^{c(g_i)}$$

其中$G=\{g_1, ..., g_s\}$ $c(g_i)$为置换$g_i$的循环节个数, $L$为本质不同的方案数, $m$ 是可以选择的颜色种数.

首先考虑旋转 :

假设当前旋转$i$颗珠子,那么就有$\gcd (n,i)$个循环,每个循环长度则为$\displaystyle \frac{n}{\gcd(n,i)}$.

这个证明同样参考了之前那篇博客....(我用 $\LaTeX$ 再打一下..)

将珠子从$0$到$n-1$标号,那么对于旋转$i$位的置换,在以$0$号为起点,长度为$t$的一个循环节,

元素标号就为$0,i \bmod n, 2i \bmod n, ... , (t-1)i \bmod n$.

所以就有$t \cdot i \bmod n = 0$,即有$t \cdot i = n \cdot k$. 使等式左右成立的最小正整数就为$\mathrm{lcm} (n, i)$.

那么$t \cdot i = \mathrm{lcm}(n,i)$所以$\displaystyle t=\frac{\mathrm{lcm}(n,i)}{i}=\frac{n}{\gcd(n,i)}$. 那么循环节个数就是$\displaystyle \frac{n}{t}=\gcd(n,i)$.

所以这些置换的贡献就是$a=\sum \limits_{i=0}^{n-1} m^{\gcd(i,n)}$.
再考虑一下翻转 :

这个要分序列奇偶性分别考虑,应该是比较好考虑的.
1. 如果长度$n$为奇数,那么我们就只能沿着一个珠子翻转,那么就有$\frac{n-1}{2}$个长度为$2$的等价类和 $1$个长度为$1$的等价类.
2. 如果长度$n$为偶数,那么我们就有两种方式.沿着两个珠子翻转,那么就有$\frac{n-2}{2}$个长度为$2$的等价类和$2$个长度为$1$的等价类. 否则我们沿着两个珠子中间来翻转,那么就有$\frac{n}{2}$个长度为$2$的等价类.
所以这些置换的贡献就是 $\displaystyle b=\begin{cases}n \cdot m^{\frac{n+1}{2}} & (m \ is \ odd)\\ \frac{n}{2}\cdot (m ^ {\frac{n}{2}+1}+m^{\frac{n}{2}}) &(m\ is\ even)\end{cases}$

这样的话似乎会漏算情况（hany01大大问了下我）然后还是前面那篇大佬博客上有解释.

就是旋转再翻转的情况,肯定是其中另一种翻转.这也是因为群有封闭性,不管怎样$*$(二元运算)都是群内的元素.

最后要除以一个$|G|$,项链只有$n$个置换群,手镯有$2n$个啦.

代码

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), _end_ = (int)(r); i <= _end_; ++i)

#define Fordown(i, r, l) for(register int i = (r), _end_ = (int)(l); i >= _end_; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

typedef long long ll;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

void File() {

#ifdef zjp_shadow

    freopen ("10294.in", "r", stdin);

    freopen ("10294.out", "w", stdout);

#endif

}

const int N = 55;

ll n, t, Pow[N], a, b;

int main () {

    File();

    while (~scanf("%lld%lld", &n, &t) && n) {

        Pow[0] = 1;

        a = b = 0;

        for (int i = 1; i <= n; ++i) Pow[i] = Pow[i - 1] * t;

        for (int i = 0; i < n; ++ i) a += Pow[__gcd(i, (int)n)];

        if (n & 1) b = n * Pow[n / 2 + 1];

        else b = n / 2 * (Pow[n / 2 + 1] + Pow[n / 2]);

        printf ("%lld %lld\n", a / n, (a + b) / 2 / n);

    }

    return 0;

}

秒客网

UVA10294 Arif in Dhaka (群论,Polya定理)

题意

题解

代码

相关文章