题目理解

题目要求计算可以制作的不同手镯的数量。手镯由 s 颗珠子组成，每颗珠子可以有 c 种不同的颜色。手镯是一个环形结构，没有起点和终点，也没有方向性（即旋转或翻转后相同的手镯视为同一种）。给定颜色数量 c 和珠子数量 s，计算可以制作的不同手镯的数量。

解题思路

这个问题属于组合数学中的计数问题，特别是涉及到对称性（旋转和翻转）的计数。可以使用Burnside引理或Polya计数定理来解决。

Burnside引理

Burnside引理指出，对于有限群 G 作用在有限集合 X 上，轨道的数量（即不同的配置数）等于群中每个元素的不动点的平均数。

对于手镯问题：

1. 旋转对称性：手镯可以旋转 0 到 s-1 个位置。
2. 翻转对称性：手镯可以沿 s 条不同的轴对称翻转。

因此，群 G 的大小为 2s（s 个旋转和 s 个翻转）。

Polya计数定理

Polya计数定理是Burnside引理的特例，直接给出了计数公式： $ \text{Number of distinct bracelets} = \frac{1}{2s} \left( \sum_{d | s} \phi(d) \cdot c^{s/d} + s \cdot c^{(s+1)/2} \right) $ 其中：

• $\phi(d)$ 是欧拉函数，表示与 d 互质的数的个数。
• 第一项处理旋转对称性。
• 第二项处理翻转对称性（分为奇数长度和偶数长度的情况）。

代码解析

代码使用了Polya计数定理来计算不同手镯的数量。以下是代码的分步解析：

1. 输入处理：

   • 使用 scanf 读取 M（颜色数 c）和 N（珠子数 s），直到输入 0 0 为止。

2. 计算旋转对称性的贡献：

   • 对于每个旋转 i（相当于旋转 i 个位置），计算旋转的周期数 tmp = GCD(N, i)。
   • 每个旋转的不动点数是 c^tmp，其中 tmp 是旋转的周期数。
   • 将所有旋转的贡献累加到 sum 中。

3. 计算翻转对称性的贡献：

   • 如果 N 是奇数：
     • 有 N 种翻转对称性（沿每颗珠子的对称轴翻转）。
     • 每种翻转的不动点数是 c^{(N+1)/2}。
   • 如果 N 是偶数：
     • 有 N/2 种翻转对称性沿珠子之间的对称轴翻转，每种贡献 c^{(N+2)/2}。
     • 有 N/2 种翻转对称性沿珠子的对称轴翻转，每种贡献 c^{N/2}。

4. 应用Burnside引理：

   • 将 sum 除以 2N（群 G 的大小），得到不同的手镯数量。

5. 输出结果：

   • 对于每个测试用例，输出计算得到的不同手镯数量。

###标程

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
 
int M,N;
 
int GCD(int a,int b)
{
    if(b == 0)
        return a;
    return GCD(b,a%b);
}
 
int main()
{
    while(~scanf("%d%d",&M,&N) && (M||N))
    {
        int sum = 0;
        for(int i = 1; i <= N; ++i)
        {
            int tmp = GCD(N,i);
            sum += (int)(pow(M*1.0,tmp*1.0));
        }
        if(N & 1)
            sum += (int)(N * pow(M*1.0, (N+1)/2.0));
        else
        {
            sum += (int)((N/2) * pow(M*1.0, (N+2)/2.0));
            sum += (int)((N/2) * pow(M*1.0, N/2.0));
        }
        sum = sum/(2*N);
        printf("%d\n",sum);
    }
 
    return 0;
}

复杂度分析

• 时间复杂度：
  • 对于每个测试用例，计算旋转对称性的贡献需要 O(N) 时间。
  • 计算翻转对称性的贡献需要 O(1) 时间。
  • 总体复杂度为 O(N) 每个测试用例。
• 空间复杂度：
  • 只使用了常数空间，O(1)。

总结

通过应用Polya计数定理，代码高效地计算了考虑旋转和翻转对称性的不同手镯数量。这种方法避免了直接枚举所有可能的配置，适用于给定的约束条件（c * s <= 32）。