「POJ2409」Let it Bead

Description


项链由nn个珠子组成,每个珠子可以染成cc种不同的颜色,试求出一共可以设计出多少种本质不同的项链。

Solution

每个珠子顺指针旋转xx布,可以证明循环节的个数有gcd(x,n)gcd(x,n)个。
假设当前位置是pp,那么他的循环是ppp+xp+x\cdotsp+kxp+kx
就是p+kxp(modn)p+kx\equiv p\pmod{n} \to kx0(modn)kx\equiv 0\pmod{n}
我们要的是kk的最小正整数解

nkxn|kx

同时

xkxx|kx

所以kx=lcm(x,n)kx=lcm(x,n) \Rightarrow k=xn÷gcd(x,n)÷x=ngcd(x,n)k=xn\div gcd(x,n)\div x=\frac{n}{gcd(x,n)}
那么p+1p+1p+2p+2直到p+x1p+x-1都是可以独立成为一个循环节。
所以枚举一个循环长度xx,那么它的循环节长度为gcd(x,n)gcd(x,n)。即

x=1ncgcd(x,n)\sum_{x=1}^{n}c^{gcd(x,n)}

至此,循环的置换可以解决了,那么翻转的。

  1. nn是奇数

    对于一个位置pp,以pp和圆心作对称轴,那么其他每一个点除了pp点,都有一个对应的,这个每个置换的循环节个数为n+12\frac{n+1}{2}nn个置换

  2. nn是偶数

    一种是以ppp+n2p+\frac{n}{2}作作对称轴,那么每个置换有n2+1\frac{n}{2}+1个循环,n/2n/2个置换
    一种是以某两个珠子的中点过圆心的情况,那么每个置换有n2\frac{n}{2}个循环。共n1n-1个,共n/2n/2个置换
    根据Pólya定理,把两部分加起来除以置换的个数就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

int c, n;
int gcd(int x, int y) {
if(!y) return x;
return gcd(y, x % y);
}
int main() {
while(1) {
c = read(), n = read();
if(!c && !n) break;
ll ans = 0;
for(int i = 1; i <= n; ++i) ans += pow(c, gcd(i, n));
if(n & 1) ans += pow(c, n / 2 + 1) * (ll)n;
else {
ans += (n / 2) * pow(c, n / 2 + 1);
ans += (n / 2) * pow(c, n / 2);
}
writeln(ans / (2 * n));
}
return 0;
}