[hdu] 4187: Alphabet Soup

发表于   |   分类于   |  

题意

　　一个圆上有$n$个点, 用$n$个角度($\pi=180000$)表示, 用$m$种颜色对n个点着色, 旋转后相同视为同一种着色方案, 求本质不同着色方案数

传送门

分析

参考【HDU】4187 Alphabet Soup - DrunBee - 博客园

代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

typedef long long ll ;


#define  sqr(x)  ((x)*(x))
#define  Rep(i,l,r) for (i=l;i<=r;i++)
#define  Rev(i,l,r) for (i=r;i>=l;i--)

#define  maxn  360010LL
#define  pi    180000LL
#define  ansmod  100000007LL

std::vector<int> factor ;

int phi[maxn] = {0} , str[maxn] , next[maxn] , data[maxn] ;

void GetPhi() {/* 得到所有phi */
int i , j ;
truephi[1] = 1 ;
trueRep (i , 2 , maxn-1) if (!phi[i]) {
truetruefor (j = i ; j < maxn ; j += i) {
truetruetrueif (!phi[j]) phi[j] = j ;
truetruetruephi[j] -= phi[j]/i ;
truetrue}
true}
}

void GetFactor(int x) {/* 得到x的所有约数 */
int i , tmp ;
truefactor.clear() ;
truefor (i = 1 ; sqr(i) <= x ; i ++ )
truetrueif (x%i == 0) {
truetruetruefactor.push_back(i) ;
truetruetrueif (sqr(i)!=x) factor.push_back(x/i) ;
truetrue}
}

void exgcd(ll a , ll b , ll& d , ll& x , ll& y) {
trueif (b) { exgcd(b , a%b , d , y , x) ; y -= x*(a/b) ; }
trueelse { d = a ; x = 1 ; y = 0 ; }
}

ll Inverse(ll a , ll m) {
ll x , y , z ;
trueexgcd(a , m , z , x , y) ;
truereturn (x%m+m)%m ;
}

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

int Next(int n) {
int i , j ;
truenext[0] = j = -1 ;
truefor (i = 0 ; i < n ; )
truetrueif (j<0 || str[i]==str[j]) next[++i] = ++j ;
truetrueelse j = next[j] ;
truei = n-next[n] ;
truereturn (n%i) ? n : i ;
}

ll Burnside(int n , int m) {
int i ; ll ret = 0 ;
trueGetFactor(n) ;
trueRep (i , 0 , factor.size()-1)
truetrueret += POW(m,factor[i])*phi[n/factor[i]] ,
truetrueret %= ansmod ;
truereturn (ret*Inverse(n,ansmod))%ansmod ;
}

int main() {
int n , m , i , len ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueGetPhi() ;
truewhile (scanf("%d%d", &m , &n) , m!=-1||n!=-1) {
truetrueRep (i , 1 , n) scanf("%d", &data[i]) ;
truetruestd::sort(data+1 , data+n+1) ;
truetrueRep (i , 1 , n-1)
truetruetruestr[i] = data[i+1]-data[i] ;
truetruestr[0] = pi*2-data[n]+data[1] ;
truetruelen = Next(n) ;
truetrueprintf("%lld\n", Burnside(n/len, POW(m,len))) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章