Invoker-n颜色涂m个珠子的项链

时间:2021-09-08 17:25:50

参考https://blog.csdn.net/anxdada/article/details/76862564、 https://blog.csdn.net/baidu_35643793/article/details/75268911

一些涂色方案项链在一些变化下G={一些旋转..,一些翻折..}等价,要找出不等价的涂色方案数,或者说等价类数。

置换所构成的元素之间的关系来表示这几种方案间等价关系。

Burnside。各种置换下不变元素(元素,方案(,,))个数之和 == 置换数乘等价类个数(不同类,类数)

各置换中不变元素(不动点)个数之和 = ∑n^循环节(置换的轮换表示看到,置换的成分 (旋转置换的循环节))的个数之和。不变元素,置换后方案没有变。也可以认为是分别保持各种元素不变的置换数之和Zk之和。2×2正方形黑白染色例子,可以认为16+2+4+2,2^4+2^1+2^2+2^1;也是4+4+1+..。等价类个数。等价的元素看放一起看作一点后的点数。

旋转置换,循环节数gcd(m, i),i为旋转角度。m/t,t为等价类中元素个数

翻折置换,奇数,循环为1,2,循环节数m/2+1;偶数循环为2,对称轴两类个m/2个,循环节数分别为过顶点m/2+1不过顶点m/2加起来。

还有除以置换种类数,因为取模,转化为求同余的结果,借用逆元,费马小定理(就用1e9+7, inv(a)=pow(a, p-2)%p)或者扩展欧几里得算法。