题目链接
3133. 串珠子
给定 \(M\) 种不同颜色的珠子，每种颜色的珠子的个数都足够多。
现在要从中挑选 \(N\) 个珠子，串成一个环形手链。
请问一共可以制作出多少种不同的手链。
注意，如果两个手链经旋转或翻转后能够完全重合在一起，对应位置的珠子颜色完全相同，则视为同一种手链。
输入格式
输入包含多组测试数据。
每组测试数据占一行，包含两个整数 \(M,N\)。
最后一行包含 0 0 表示输入结束。
输出格式
每组数据输出一个占一行的整数表示结果。
数据范围
\(N,M > 0\),
\(N \times M \le 32\)
输入样例：
1 1
2 1
2 2
5 1
2 5
2 6
6 2
0 0
输出样例：
1
2
3
5
8
13
21
样例解释
当 \(M=2,N=5\) 时，一共可以制作出 \(8\) 种不同的手链，如下图。
解题思路
polya
burnside引理：设 \(A\) 和 \(B\) 为有限集合， \(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合。
\(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。
\(X / G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合
(若 \(X\) 中的两个映射经过 \(G\) 中的置换作用后相等，则它们在同一等价类中)，则
其中 \(|S|\) 表示集合 \(S\) 中元素的个数，且
\[X^g=\{x \mid x \in X, g(x)=x\} \]burnside引理的直观理解：每种置换的不动点个数的平均值，即本质不同的方案数
polya定理：在与 Burnside 引理相同的前置条件下，若 \(X\) 为 所有从 \(A\) 到 \(B\) 的映射，内容修改为
其中 \(c(g)\) 表示置换 \(g\) 能拆分成的不相交的循环置换的数量
polya定理即求每种置换的不动点个数，但是必须保证其拆分的循环置换不相交
本题有两种置换：旋转和翻转
对于旋转来说，方向没有影响，假设都顺时针旋转，对于每个点来说旋转可以每次旋转 \(0,1,2,\dots,n-1\) 次，每次旋转 \(k\)，设旋转 \(t\) 次后 \(i\) 回到原位置，即 \(i+k\times t\equiv i(\bmod n)\)，解得 \(t=n/gcd(k,n)\)，即每个轨迹的点数，对于 \(i+1\) 这个点来说每次旋转 \(k\) 次，跟 \(i\) 这个点的轨迹不会相交，且轨迹上的点数和 \(i\) 相等，即所有不相交的轨迹点数相等，总共有 \(n/t=gcd(k,n)\) 条不相交的轨迹
对于翻转来说，如果 \(n\) 为奇数，讨论其对称轴，共有 \(n\) 个对称轴，即 \(n\) 个置换群，考虑经过轴上的那个点，每个置换群共有 \(\frac{n+1}{2}\) 个循环置换；如果 \(n\) 为偶数，对称轴细分为是否经过点，对于经过点的对称轴，其共有 \(\frac{n}{2}\) 个置换群，每个置换群有 \(2+\frac{n-2}{2}=\frac{n}{2}+1\) 个循环置换，对于不经过点的对称轴，其也有 \(\frac{n}{2}\) 个置换群。每个置换群有 \(\frac{n}{2}\) 个循环置换
故总的方案数为
- 时间复杂度：\(O(logn)\)
代码
// Problem: 串珠子
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/3136/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int m,n;
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res*=a;
a*=a;
b>>=1;
}
return res;
}
int main()
{
while(cin>>m>>n,m||n)
{
int res=0;
for(int i=0;i<n;i++)res+=ksm(m,__gcd(i,n));
if(n&1)
res+=n*ksm(m,n+1>>1);
else
res+=n/2*ksm(m,n/2+1)+n/2*ksm(m,n/2);
cout<<res/(2*n)<<'\n';
}
return 0;
}