算法合集之《置换群快速幂运算研究与探讨》.ppt
《算法合集之《置换群快速幂运算研究与探讨》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《置换群快速幂运算研究与探讨》.ppt(28页珍藏版)》请在三一文库上搜索。
1、1,置换群快速幂运算 研究与探讨,江苏省苏州中学 潘震皓,2,基础知识,群 是集合G和定义在G上的二元运算符 组成的代数系统 群 满足 封闭性、结合律、单位元和逆元,基础知识,置换 置换T 定义符号 ,a被b取代 = b=aT a()2T= aTT,排列,基础知识,连接运算 aT1T2 = a(T1T2),基础知识,循环,6,置换群基本操作 存储 映射 连接运算 分解循环 整幂运算 开方运算,O(n),O(1),O(n),O(n),?,O(nlogk),?,O(n+k),O(n+k),!,!,例题,洗牌机 (CEOI 98) 剀剀和凡凡有N张牌(依次标号为1,2,N)和一台洗牌机。假设N是奇数
2、。洗牌机的功能是进行如下的操作:对所有位置I(1IN),如果位置I上的牌是J,而且位置J上的牌是K,那么通过洗牌机后位置I上的牌将是K。 剀剀首先写下一个1N的排列ai,在位置ai处放上数值ai+1的牌,得到的顺序x1, x2, ., xN作为初始顺序。他把这种顺序排列的牌放入洗牌机洗牌S次,得到牌的顺序为p1, p2, ., pN。现在,剀剀把牌的最后顺序和洗牌次数告诉凡凡,要凡凡猜出牌的最初顺序x1, x2, ., xN。,例题,位置i 扑克牌j 位置j 扑克牌k 位置i 扑克牌k ai 位置ai 扑克牌ai+1 (1 3 4 2),位置,牌,一个引子,设 ,(T为一循环,e为单位置换),
3、那么k的最小正整数解为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)b a=gcd(n,k) b=k/a Tk=(Ta)b,所以说,现在问题就转换到了长度n和指数k互质时 的 整幂运
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 置换群快速幂运算研究与探讨 算法 置换 快速 运算 研究 探讨
链接地址:https://www.31doc.com/p-2122561.html