[poj] 2409: Let it Bead

发表于   |   分类于   |  

题意

用k种颜色对n个珠子构成的环上色, 旋转翻转后相同的只算一种, 求本质不同的着色方案数

传送门

分析

对于翻转使用 $burnside$ 定理

当$n$为奇数时有一种情形

$n$个翻转都为以某一顶点和它所对的边的中点为轴翻转的,着色方案数为$$k^{n/2+1}\cdot n$$种

当$n$为偶数时有两种情形

有$n/2$个翻转是以对顶点为轴旋转的,共$$k^{n/2+1}\cdot n/2$$种

　

另外$n/2$个翻转是以对边中点为轴旋转的,共$$k^{n/2}\cdot n/2$$种

对于旋转使用 $burnside$ 定理计算的优化 $polya$ 计数公式
即

$$\sum_{i=1}^{n}k^{gcd(n,i)}$$

最后再除以置换群的大小$n\cdot2$

代码

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
#include <cstdio>

typedef long long ll ;

inline ll POW(ll x , ll p) {
truell ret = 1 ;
truefor ( ; p ; p>>=1 , x *= x) if (p&1) ret *= x ;
truereturn ret ;
}

inline int GCD(int x , int y) {
truereturn y ? GCD(y , x%y) : x ;
}

int main() {
int n , k , i ;
ll ans ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
truewhile (scanf("%d%d", &k , &n)&&n&&k) {
truetrueif (n&1) ans = POW(k , n/2+1)*n ;
truetrueelse ans = POW(k , n/2+1)*(n/2)+POW(k,n/2)*(n/2) ;
truetruefor (i = 1 ; i <= n ; i ++ )
truetruetrueans += POW(k , GCD(n , i)) ;
truetrueprintf("%lld\n", ans/(2*n)) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章