华为用的这个， 其实是个杭电的题目：
题目链接：hdu 3923 Invoker
dota游戏里面，召唤师可以控制冰雷火三种元素，并通过元素组合产生新的技能。
现在我们修改了张新的地图， 地图中他能够控制n种元素， 并且将m个元素围成一个圈组成一 个新技能(这m个元素通过旋转或反转，算作重复，如123、231、312、 321、213、 132都算重复)，那么召唤师能组合多少技能(20000>=n>=1 ,1<=m<=10000)，由于结果可能很大，请将结果对1000000007取余
- 先从n个不同元素里面选择m个元素，得到选择的种类数，
- 用n个元素去填满m个空位槽，填法通过旋转或者翻转，都算作重复
假设m是3，那么，可以旋转0度，120度，240度
旋转0度：
(
1
2
3
1
2
3
)
\begin{pmatrix} 1 & 2 &3 \ 1 & 2&3\end{pmatrix}
(112233)，循环节3
旋转120度：
(
1
2
3
3
2
1
)
\begin{pmatrix} 1 & 2 &3 \ 3&2&1\end{pmatrix}
(132231)，循环节2，
旋转240度：
(
1
2
3
2
3
1
)
\begin{pmatrix} 1 & 2 &3 \ 2 & 3&1\end{pmatrix}
(122331)，循环节1
可以看作用m个元素去填满n个空位，
其实它这里没有说的很清楚，112，322，133 这种包含了相同元素的组合也是可以的，困扰了我非常久，我觉得还是看珠子涂色问题比较清楚
杭电的题目里面详细解释了用例
For Case #1: we assume a,b,c are the 3 kinds of elements.
Here are the 21 different arrangements to invoke the skills
/ aaaa / aaab / aaac / aabb / aabc / aacc / abab /
/ abac / abbb / abbc / abcb / abcc / acac / acbc /
/ accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc /
Output： 输出组合的技能数。
Sample Input
3 4
1 2
Sample Output
Case #1: 21
Case #2: 1
答案来源：https://cloud.tencent.com/developer/article/1179882
不使用欧拉和质数表进行优化的话，会直接TimeOut，
而且面对大数时，有符号数溢出，会直接变成负数，
#include使用Polay定理即可，详情看下面解析：
Polya定理：设有n个对象，G是这n个对象上的置换群，用m种颜色涂染这n个对象，每个对象涂染一种颜色。
若一种染色方案在群G的作用下变为另一种方案，则这两种方案当作是一种方案。
那么存在的方案个数为
L
L
L，根据公式：
c(ai)是置换ai的循环节数。
m
c
(
a
i
)
=
c
1
(
p
i
)
m^{c(ai)} = c1(pi)
mc(ai)=c1(pi)
- 置换群G
- 置换Gi的不动点个数（循环节为1的点数）: c 1 ( p i ) c1(pi) c1(pi)
- 循环节： c ( a i ) c(ai) c(ai)
- 着色方案数计算
对2*2的方阵用黑白两种颜色涂色，问能得到多少种不同的图像？经过旋转使之吻合的两种方案，算是同一种方案。
-
若一种染色方案在置换群G的作用下变为另一种方案：
例如：
正方形C3旋转180度，变成正方形C5 ，说明在旋转180度这个置换下，C3和C5等价、
可以知道对正方形而言，旋转的情况有，旋转90度，旋转180度，旋转270度，旋转0度，所以置换群G为： 置 换 群 G = { 旋 转 90 度 ， 旋 转 180 度 ， 旋 转 270 度 ， 旋 转 0 度 } 置换群G=\{旋转90度，旋转180度，旋转270度，旋转0度\} 置换群G={旋转90度，旋转180度，旋转270度，旋转0度} -
c1(“旋转90度”)是置换旋转90度 的不动点的个数(
既循环节为1的点数)：
例如：
可知下面的16种情况中：
转90度时，正方形C3转90度可以得到C6的图形，C6转90度得到C5，以此类推，所以(把C6表示为6，C3表示为3)可以写出
可以看出：旋转90度时，3可以置换为6，6可以置换为5，5置换为4，4置换为3，回到了3，是一个循环。
所以，把循环写在一起：（3,6,5,4)(1)(2)(8,7,10,9)(11,12)(13,16,15,14)
找不动点（循环里只有一个元素的集合），可以看出旋转90度的不动点是(1)、(2)，
同理：
转180度时，3可以置换为5，5可以置换为3，是一个循环，
类似的，有(1)(2)(3,5)(4,6)(7,9)(8,10)(11)(12)(13,15)(16,14)
所以正方形进行旋转180度的变换时，不动点为(1)(2)(11)(12)
所以，
旋转0度有16个不动点，
旋转90度有2个不动点，
旋转180度有4个不动点，
旋转270度有2个不动点， -
循环节： c ( a i ) c(ai) c(ai)
方格可以 旋转 0° , 90 ° , 180 ° ,270° . 所以 群G = { 0° , 90 ° , 180 ° ,270° } , G的阶|G| = 4 ,
可知
G1置换{转0° }= ( 1 2 4 3 1 2 4 3 ) \begin{pmatrix} 1 & 2 &4 &3 \ 1 & 2&4&3 \end{pmatrix} (11224433)
G2置换{转90° }= ( 1 2 4 3 3 1 2 4 ) \begin{pmatrix} 1 & 2 &4 &3 \ 3 & 1&2&4 \end{pmatrix} (13214234)
G3置换{转180° }= ( 1 2 4 3 4 3 1 2 ) \begin{pmatrix} 1 & 2 &4 &3 \ 4 & 3&1&2 \end{pmatrix} (14234132)
G4置换{转270° }= ( 1 2 4 3 2 4 3 1 ) \begin{pmatrix} 1 & 2 &4 &3 \ 2 & 4&3&1 \end{pmatrix} (12244331)
所以：G1置换（旋转0° ）中，1旋转0° 后得到1，2旋转0° 得到2，3进行G1置换后（旋转0° ）得到3，4置换后得到4，循环节为(1)(2)(3)(4)，总共有4个G2置换（旋转90° ）中，
位置1旋转90° 得到3，位置3旋转90° 得到4，4旋转90° 得到2，2旋转90° 得到1，回到了1，是一个循环。所以：
G2置换（旋转90° ）的循环节为（1，3，4，2）
同理：G3置换（旋转180° ）中，1旋转180° 后得到4，4旋转180° 得到1，是一个循环（1，4）；
2进行G3置换后（旋转180° ）得到3，3置换后得到2，得到循环（2，3）
循环节为(1，4)(2，3)
G1置换{转0° }的循环节是4个。{ (1),(2),(3),(4) }
G2置换{转90° }的循环节是1， { （1，3，4，2） }
G3置换{转180°}的循环节是2， { (1,4),(2,3) }
G4置换{转270°}的循环节是1。{ (1,2,4,3) }
-
着色方案数量计算：
可知，|G| = 4（对应四种旋转角度）
置换Gi的不动点个数（循环节为1的点数）:
c 1 ( p 1 : 0 ° ) = 16 , c1(p1:0°) = 16, c1(p1:0°)=16,
c l ( p 2 ： 90 ° ) = 2 ， cl(p2：90°)= 2， cl(p2：90°)=2，
c l ( p 3 ： 180 ° ) = 4 ， cl(p3：180°)=4， cl(p3：180°)=4，
c l ( p 4 ： 270 ° ） = 2 cl(p4：270°）=2 cl(p4：270°）=2
置换Gi的循环节个数：
c ( p 1 : 0 ° ) = 4 , c(p1:0°) = 4, c(p1:0°)=4,
c ( p 2 ： 90 ° ) = 1 ， c(p2：90°)= 1， c(p2：90°)=1，
c ( p 3 ： 180 ° ) = 2 ， c(p3：180°)=2， c(p3：180°)=2，
c ( p 4 ： 270 ° ） = 1 c(p4：270°）=1 c(p4：270°）=1所以
L = 1 ∣ G ∣ ∗ [ 16 + 2 + 4 + 2 ] = 1 ∣ G ∣ ∗ [ 2 4 + 2 1 + 2 2 + 2 1 ] = 6 L = \frac{1}{|G|}* [16 + 2 + 4 + 2] = \frac{1}{|G|} *[ 2^4 + 2^1 + 2^2 + 2^1 ] = 6 L=∣G∣1∗[16+2+4+2]=∣G∣1∗[24+21+22+21]=6得到最后方案数 6种。
可以看出，如果要计算 置换Gi的不动点个数（循环节为1的点数）会特别麻烦，所以最好直接通过知道置换Gi的循环节个数来进行计算比较好，那么，怎么求一个置换的循环节数？
- 方法一：把所有置换写出来，就能知道它们的循环节数了。
- 方法二：现成公式，对于旋转，有c(ai) = gcd(n,i)，i为转动幅度，1~n，gcd是求最大公约数。
典型题目：用2种颜色去染排成一个环的6个棋子，如果通过旋转得到则只算一种，一共有多少种染色方案？
典型的满足polya公式的条件，m=2，n=6。
因为是旋转得到的置换，所以存在6个置换（自己置换到自己也算）。
每个置换的循环节已经标出了。
所以根据polya定理公式可以算出，染色方案数为
(
2
6
+
2
1
+
2
2
+
2
3
+
2
2
+
2
1
)
/
6
(2^6+2^1+2^2+2^3+2^2+2^1)/6
(26+21+22+23+22+21)/6 = 14
POJ2409：
题意：一家项链公司生产手镯。
n颗珠子形成一个环，用m种颜色给n颗珠子染色，就得到了各种各样的手镯。
但是，经过旋转和翻转使之吻合的算同一种方案。
例如，当用2种颜色对5颗珠子进行染色的方案数为8，
1.对于旋转：有c(gi) = gcd(n,i)，i为转动几颗珠子。
gcd是求最大公约数。
2. 对于翻转，当n为奇数时，c(gi) = （n/2）+1；当n为偶数时，n个置换里，有n/2个置换的循环节数为（n/2）+1，有n/2个置换的循环节数为n/2。
所以，计算旋转得到的方案种类数，再计算翻转得到的方案种类数，最后除以（n*2）
计算a,b的最大公约数：
int gcd(int a, int b)
{
return b==0?a:gcd(b,a%b);
}
c++
#include Kaleidoscope(HDU-6360)(Polya定理)
题目大意：给你一个菱形6面体(共60面),然后给你 n nn 种颜色给它每一个面上色，要求第 i ii 种颜色必须至少涂 c [ i ] c[i]c[i] 次,问你本质不同的方案数，旋转相同视作同一种方案，染色方案数对 p pp 取模，多组数据
数据范围：
https://blog.csdn.net/ojshilu/article/details/15378645
http://t.zoukankan.com/bhlsheji-p-4747427.html
https://www.iteye.com/blog/yzmduncan-1402942
https://blog.csdn.net/qq_37555704/article/details/88073792
https://blog.csdn.net/liangzhaoyang1/article/details/72639208
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）