【poj2409】Let it Bead Polya定理
用 $c$ 种颜色去染 $r$ 个点的环,如果两个环在旋转或翻转后是相同的,则称这两个环是同构的。求不同构的环的个数。 $r·c\le 32$ 。
题解
Polya定理
Burnside引理:一个置换群的等价类数目等于这个置换群中所有置换的不动点数目的平均值;
Polya定理:设有限群G有 $m$ 个置换,第 $i$ 个置换有 $a_i$ 个循环,现在要将所有的点染成 $c$ 种颜色,那么染色后群G的等价类数目为:$L=\frac{c^{a_1}+c^{a_2}+…+c^{a_m}}m$ 。
推导过程:显然对于第 $i$ 个置换来说,不动点要求所有循环的颜色相同,每个循环有 $c$ 种颜色选择,所以该置换的不动点数目为 $c^{a_i}$ 。
那么考虑每种置换的循环数目:
如果没有翻转操作:设旋转 $k$ 个位置,考虑一个循环的大小 $x$ ,实际上就是 $kx\mod r=0$ 的最小正整数解(转了 $x$ 次后回到原处)。
显然 $x=\frac{\text{lcm}(k,r)}{k}=\frac{r}{\gcd(k,r)}$ ,因此循环个数为 $\frac{r}{\frac{r}{\gcd(k,r)}}=\gcd(k,r)$ ,方案数为 $c^{\gcd(k,r)}$ ;
如果有翻转操作:对于任意的 旋转-翻转-旋转 操作都等同于一次翻转操作。因此只需要统计所有本质不同的翻转操作的答案。
当 $r$ 为奇数时,对称轴为 某点-对边中点 ,显然这样置换有 $r$ 种,每个置换有 $\frac{r+1}{2}$ 个循环。因此答案为 $rc^{\frac{r+1}{2}}$ ;
当 $r$ 为偶数时,对称轴为 某点-对点 时,置换有 $\frac r2$ 种,每个置换有 $\frac r2+1$ 个循环;对称轴为 某边-对边中点 时,置换有 $\frac r2$ 种,每种置换有 $\frac r2$ 个循环。因此答案为 $\frac r2(c^{\frac r2}+c^{\frac r2+1})$ 。
把这两部分加起来即为答案。
#include <cstdio> typedef long long ll; int gcd(int a , int b) { return b ? gcd(b , a % b) : a; } int main() { int n , m , i , d; ll ans , t; while(~scanf("%d%d" , &m , &n) && (n || m)) { ans = 0; for(i = 1 ; i <= n ; i ++ ) { t = 1 , d = gcd(i , n); while(d -- ) t *= m; ans += t; } if(n & 1) { t = n; for(i = 1 ; i <= n / 2 + 1 ; i ++ ) t *= m; ans += t; } else { t = n / 2; for(i = 1 ; i <= n / 2 ; i ++ ) t *= m; ans += t; t = n / 2; for(i = 1 ; i <= n / 2 + 1 ; i ++ ) t *= m; ans += t; } printf("%lld\n" , ans / 2 / n); } return 0; }
相关文章
- 阿里云首家通过《可信云·云成本优化工具能力要求》评估,云原生企业 IT 成本治理方案助力企业 FinOps 落地
- 整合zuul启动时报错Correct the classpath of your application so that it contains a single, compatible version of XXX
- 报错Correct the classpath of your application so that it contains a single, compatible version of…
- 【学亮IT手记】AngularJS增删改查服务请求+代码剥离封装抽取示例
- SAP CRM One Order object type in line item - when it is filled
- IT运维安全的那些事?
- Atitit prgrmlan 编程语言主题列表 0 it impttech topicprgrmlan topic编程语言专题AOP拦截器 表达式写法.docx 0 it impttec
- Atitit 信息处理设备与历史与趋势 目录 1. It设备简史与艾提拉觉得常见重要的设备2 2. 第一部分 IT萌芽期(约公元前4000年至1945年)2 2.1. 苏美尔人的象形文字(约公元
- 【Codeforces Round #185 (Div. 2) A】 Whose sentence is it?
- [OHOS ERROR] clang not found, install it please
- The specified Android SDK Build Tools version (29.0.0) is ignored, as it is below the minimum suppor
- 这么多推崇学 Python 入 IT 行的,如果他们学完 Python 这一套找不到工作怎么办?
- IT人员啊,牛年发短信要有技术含量啊。。。
- IT界含金量高的认证考试
- 27岁了,目前从事软件测试,听说测试前途是IT里最差的,是这样吗?
- IT岗位中最“和谐”的两个工种:开发、测试趣谈
- 给学习IT、编程者的看
- 【TDengine】解决 connectex: No connection could be made because the target machine actively refused it.
- 零基础的小白从IT培训班出来后,是如何成为程序员,在IT行业发展的?
- 疫情之下,IT人的就业机会和薪资待遇为什么反而更好了?