算法合集之置换群快速幂运算研究与探讨.pptx

1 1置换群快速幂运算研究与探讨江苏省苏州中学潘震皓 2 2基础知识群 是集合G和定义在G上的二元运算符 组成的代数系统群 满足 封闭性、结合律、单位元和逆元基础知识置置置置换换 置置换换T T 定定义义符号符号 ，a a被被b b取代取代 =b=aT=b=aT a()a()2 2T=aTTT=aTT基础知识连连接运算接运算接运算接运算 aT1T2=a(T1aT1T2=a(T1 T2)T2)基础知识循循环环6 6置换群基本操作1.存储2.映射3.连接运算4.分解循环5.整幂运算6.开方运算O(n)O(1)O(n)O(n)?O(nlogk)?O(n+k)O(n+k)!例题洗牌机洗牌机 (CEOI 98)(CEOI 98)剀剀剀剀和凡凡有和凡凡有N N张张牌（依次牌（依次标标号号为为1 1，2 2，N N）和一台洗牌机。假）和一台洗牌机。假设设N N是奇数。洗牌机的功能是奇数。洗牌机的功能是是进进行如下的操作：行如下的操作：对对所有位置所有位置I I（1IN1IN），如），如果位置果位置I I上的牌是上的牌是J J，而且位置，而且位置J J上的牌是上的牌是K K，那么，那么通通过过洗牌机后位置洗牌机后位置I I上的牌将是上的牌将是K K。剀剀剀剀首先写下一个首先写下一个1N1N的排列的排列a ai i，在位置，在位置a ai i处处放上放上数数值值a ai+1i+1的牌，得到的的牌，得到的顺顺序序x x1 1,x,x2 2,.,x,.,xN N作作为为初初始始顺顺序。他把序。他把这这种种顺顺序排列的牌放入洗牌机洗牌序排列的牌放入洗牌机洗牌S S次，得到牌的次，得到牌的顺顺序序为为p p1 1,p,p2 2,.,p,.,pN N。现现在，在，剀剀剀剀把牌的最后把牌的最后顺顺序和洗牌次数告序和洗牌次数告诉诉凡凡，要凡凡凡，要凡凡猜出牌的最初凡猜出牌的最初顺顺序序x x1 1,x,x2 2,.,x,.,xN N。例题 位置i 扑克牌j 位置j 扑克牌k 位置i 扑克牌k ai 位置ai 扑克牌ai+1 (1 3 4 2)位置位置牌牌一个引子设设 ，（，（T T为为一循一循环环，e e为单为单位置位置换换），），那么那么k k的最小正整数解的最小正整数解为为T T的的长长度。度。T=(1 3 5 2 4 6)T=(1 3 5 2 4 6)T2=(1 5 4)(2 6 3)T2是两个循环的乘积，这两个循环分别是循环T的奇数项和偶数项T=(1 3 5 2 4 6)T3=(1 2)(3 4)(5 6)T3是三个循环的乘积，这三个循环分别是循环T中编号 mod 3=0,1,2的项当k|n时，Tk分裂成了 k个循环的乘积，这k个循环分别是循环T中编号 mod k=0,1k-1的项，按顺序的连接Ta*b=(Ta)ba=gcd(n,k)b=k/aTk=(Ta)b所以说，现在问题就转换到了长度n和指数k互质时 的 整幂运算。若 ，假设则：，显然，所以，令 ，置换群整幂运算可以在线性时间复杂度内解决算法：分解循分解循环环从每个未从每个未扫扫描元素，按上述方法求得一个循描元素，按上述方法求得一个循环环将所有求得循将所有求得循环环合并成置合并成置换换开方运算开方运算比整幂运算复杂1.有多解有多解2.有无解有无解3.多解多解规规律性不律性不强强需要解决的问题1.一个可行解一个可行解2.解的个数解的个数T=(1 6 4)(2 3 5)T1=(1 4 6)(2 5 3)T2=(1 2 6 3 4 5)T3=(1 3 6 5 4 2)T12=T22=T32=T(1 6 4)(3 5 2)T=(1 3 4 2)T=(1 3 4 2)经过经过枚枚举举，不存在一个，不存在一个T T1 1满满足足T T1 12 2=T=TT=(1 3 4 2)(5 7 6 8)T=(1 3 4 2)(5 7 6 8)T T1 1=(1 5 3 7 4 6 2 8)=(1 5 3 7 4 6 2 8)，满满足足T T1 12 2=T=T如果如果gcd(n,k)1gcd(n,k)1，那么开方，那么开方时时就必就必须须找找k k个个长长度皆度皆为为n n的循的循环环合并合并 (k(k是是gcd(n,k)gcd(n,k)的倍数，同的倍数，同时时是是k k的因数的因数)；否；否则则，不能，不能进进行开方运算行开方运算可行解生成的算法：将置将置换换分解成循分解成循环环对对于每个可以不合并的循于每个可以不合并的循环环，进进行整行整幂幂运算的运算的逆运算逆运算对对于必于必须须合并的循合并的循环环，每次，每次选择选择gcd(n,k)gcd(n,k)个合并个合并将所得到的循将所得到的循环环化化为为置置换换多解的产生1.合并与不合并之合并与不合并之间间2.选择选择几个循几个循环环合并合并3.选择选择哪几个循哪几个循环环合并合并4.合并合并时时的的“圆组圆组合合”T=(1 6 4)(2 3 5)T1=(1 4 6)(2 5 3)T2=(1 2 6 3 4 5)T3=(1 3 6 5 4 2)T12=T22=T32=T(1 6 4)(3 5 2)多解的产生1.合并与不合并之合并与不合并之间间2.选择选择几个循几个循环环合并合并3.选择选择哪几个循哪几个循环环合并合并4.合并合并时时的的“圆组圆组合合”例题单个循环，长度奇数指数是2的幂次总结置置换换群的群的幂幂运算运算这这一一问题问题是从最后一个例子洗牌是从最后一个例子洗牌机想到的，机想到的，这这一切都是一切都是对问题对问题的深入研究的深入研究带带来的来的结结果；分裂是自然而然的，而合并却是我果；分裂是自然而然的，而合并却是我们们自己自己捏出来的，捏出来的，这这一切又都是思想逆一切又都是思想逆转转所造成的所造成的结结果；果；通通过过分裂和合并，置分裂和合并，置换换群的群的幂幂运算被完美地解决运算被完美地解决了，了，这这一切又都是多一切又都是多举举例子多作猜想而得到的例子多作猜想而得到的结结果。果。每当每当发现问题发现问题，探，探寻问题寻问题，解决，解决问题问题的的时时候，我候，我们们就会找到就会找到进进步的道路。而完成步的道路。而完成这这一切一切时时，我，我们们就就进进步了。步了。谢谢大家排列矩阵(Permutation Matrix)每行每列有且每行每列有且仅仅有一个元素有一个元素值值非零非零此此值为值为1 1稀疏矩稀疏矩阵阵可以被表示可以被表示为为少量排列矩少量排列矩阵阵的和的和O(n3logk)=O(n+k)O(nm+km)