网站要怎样做才能获得市场份额,山东再发紧急通知,乐云seo官网,海口百度seo题意 用k种颜色对n个珠子构成的环上色#xff0c;旋转翻转后相同的只算一种#xff0c;求不等价的着色方案数。 思路 Polya定理 X是对象集合{1, 2, ……, n}#xff0c; 设G是X上的置换群#xff0c;用M种颜色染N种对象#xff0c;则不同的染色方案数为#xff1a; λ(g)…题意 用k种颜色对n个珠子构成的环上色旋转翻转后相同的只算一种求不等价的着色方案数。 思路 Polya定理 X是对象集合{1, 2, ……, n} 设G是X上的置换群用M种颜色染N种对象则不同的染色方案数为 λ(g)表示置换g的轮换个数且λ(g) λ1(g) λn(g) …… λn(g)其中λi(g)表示g中长度为i的轮换循环个数. 本题是对一个n个珠子的圆珠的颜色而圆珠的置换群有 Ⅰ翻转1.当n为奇数时有n种翻转每种翻转的轴都是一个顶点和该顶点对边中点的连线有n种置换每种置换的轮换个数均为(n/21)。 2.当n为偶数时有n种翻转其中n/2种转轴是两个对应顶点连线轮换个数为n/21另n/2种转轴是两条对边中点的连线轮换个数为n/2。 Ⅱ旋转枚举旋转角度360/n*i有n种旋转第i种旋转有gcd(n, i)个轮换每个轮换的长度都是n/gcd(n, i)。 然后带入公式即可. 代码 [cpp] #include iostream #include cstdio #include cmath #include algorithm #include string #include cstring #include vector #include set #include stack #include queue #define MID(x,y) ((xy)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i begin; i end; i ) using namespace std; int gcd(int a, int b){ return b?gcd(b, a%b):a; } int main(){ //freopen(test.in, r, stdin); //freopen(test.out, w, stdout); int c, s; while(scanf(%d %d, c, s) ! EOF){ long long res 0; if (c s 0) break; if (s % 2 1){ res (long long)s * pow(c, s/21); } else{ res (long long)(s/2) * (pow(c, s/2) pow(c, s/21)); } for (int i 1; i s; i ){ res (long long)pow(c, gcd(s, i)); } printf(%I64d\n, res/2/s); } return 0; } [/cpp] 转载于:https://www.cnblogs.com/AbandonZHANG/p/4114132.html
