2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/26 00:23] wzx27 创建 |
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 02:34] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | ==== 理论 ==== | ||
| === 置换的定义 === | === 置换的定义 === | ||
| 设$X$是有限集。不失一般性，取$X$为有前n个正整数组成的集合$\{1,2,...,n\}$。$X$的**置换**$i_1,i_2,...,i_n$可以看成是$X$到自身的一一映射，其定义为： | 设$X$是有限集。不失一般性，取$X$为有前n个正整数组成的集合$\{1,2,...,n\}$。$X$的**置换**$i_1,i_2,...,i_n$可以看成是$X$到自身的一一映射，其定义为： | ||
| 行 21: | 行 22: | ||
| === 置换的幂运算 === | === 置换的幂运算 === | ||
| 参考文献: | 参考文献: | ||
| - | *《2005信息学国家集训队论文：置换群快速幂运算 研究与探讨》——潘震皓* | + | //《2005信息学国家集训队论文：置换群快速幂运算 研究与探讨》——潘震皓// |
| 对任意置换$T$，可对其进行循环分解，如 | 对任意置换$T$，可对其进行循环分解，如 | ||
| 行 27: | 行 28: | ||
| 显然有如下性质：对置换$T$，$T^k=\iota$的最小正整数解为$T$中所有循环长度的最小公倍数 | 显然有如下性质：对置换$T$，$T^k=\iota$的最小正整数解为$T$中所有循环长度的最小公倍数 | ||
| - | 对置换的整幂运算$T^n$，感觉用快速幂$O(nlogk)$就行惹（~~其实是因为论文中的$O(n)$算法没看懂~~ | + | 特别地，当$T$为单循环时，则$T^k=\iota$的最小正整数解为$T$的循环长度$l$ |
| - | 对置换的分数幂运算（开方）就很有意思了 | + | 对置换的整幂运算$T^n$，感觉用快速幂$O(nlogk)$就行（<del>其实是因为论文中的算法没看懂</del> |
| + | |||
| + | 对置换的分数幂运算（开方） | ||
| 分两种情况： | 分两种情况： | ||
| - | 循环长度和指数互质： | + | |
| + | 单循环：如果循环长度和指数互质则能开方，否则不能 | ||
| + | |||
| + | 多循环：取$m=gcd(l,k)$个长度相同的循环合并，如果某个长度的循环数不能被$m$整除则不能开方 | ||
| + | |||
| + | ==== 题目 ==== | ||
| + | 1、置换群中的循环 | ||
| + | |||
| + | [[https://vjudge.net/problem/POJ-1026|poj1026 Cipher]] | ||
| + | |||
| + | 每次给出一个置换，再给出多个字符串，如果字符串长度为$k$则对字符串的下标置换k次（空出来的地方填空格），然后输出新的字符串 | ||
| + | |||
| + | 不用置换群的知识就硬模拟都行，找出置换群里的每个循环，然后模拟即可 | ||
| + | |||
| + | [[https://vjudge.net/problem/POJ-3270|poj3270 Cow Sorting]] | ||
| + | |||
| + | 一个两两不同的序列$a[i]$，可以交换$a[i],a[j]$的值，花费为$a[i]+a[j]$，问如何花费最少的代价使得序列边为升序 | ||
| + | |||
| + | 记排序后的序列的下标序列为$p$，则可以构造原下标对应$p$一个置换 | ||
| + | $$\left (\begin{array}{c} 1&2&...&n\\p_1&p_2&...&p_n\end{array}\right)$$ | ||
| + | 求出置换中所有的循环，考虑每个循环中交换的花费。记某个循环中所有下标对应最小的值为$mi$，循环长度为$len$，该循环中所有下标对应值的和为$sum$，所有序列中的最小值为$low$，则每个循环的最小花费为$$min\{sum+mi\times (len-2),\; sum+mi+low\times (len+1)\}$$ | ||
| + | 其含义为：每个循环中的最小元素分别去交换其他元素使得其他元素在合适位置，或者先让循环内的最小元素和全局的最小元素交换再分别交换循环内的其他元素，结束后重新交换回循环内的最小元素。正确性挺显然的（bushi | ||
| + | |||
| + | [[https://vjudge.net/problem/UVA-11077|uva11077 Find the Permutations]] | ||
| + | |||
| + | 问长度为n的所有排列里有多少种排列能在最少交换$m$次的情况下变成$1,2,...,n$ | ||
| + | |||
| + | 把每个排列都看出一个置换，最少交换次数的贡献来源于置换中的每个循环，交换次数=每个循环的长度-1的和 | ||
| + | |||
| + | 定义$f[i][j]:=长度为n的所有排列中，最少交换次数为j的排列个数$，于是有$f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1)$ | ||
| + | |||
| + | [[https://vjudge.net/problem/POJ-3590|poj3590 The shuffle Problem]] | ||
| + | |||
| + | 问长度为$n$的置换$T$，使得$T^k=\iota$的最小正整数解$k$最大的$T$是什么 | ||
| + | |||
| + | 有上述定理可知$T^k=\iota$的最小正整数解为$T$中所有循环的最小公倍数，这个显然能通过$\text{dp}$求得。记$f[i][j]:=和为i的j个数的lcm$，于是$f[i][j]=max\{f[i-1][j-k]*k/gcd(f[i-1][j-k],k)\}$ | ||
| + | |||
| + | 从而能得到长度为$n$的置换的解$\text{maxlcm}$,并唯一分解得到$maxlcm=\prod p_i^{k_i}$且$\sum p_i^{k_i}\le n$，所以拆成大小为$p_i^{k_i}$的循环，剩下的都是长度为1的循环即可 | ||
| + | |||
| + | 2、置换群的幂运算 | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P2227|P2227 洗牌机]] | ||
| + | |||
| + | 已知$T^{2^s}$求$T$，保证$T$为单循环且长度为奇数 | ||
| + | |||
| + | 相当于$T$做了平方运算后，再讲得到的新置换继续平方，一共操作$s$次。因为长度为奇数，所以平方过程中不会分裂，始终保持单循环。再由定理$T^k=\iota$的解是$l$的整数倍，所以如果有$2^t \equiv 1 \pmod l$，那么$T^{2^t}=T$，即$T^{2^{(t-s\%t)}}=T$ | ||
| + | |||
| + | 又$2^t \equiv 1 \pmod l$在小于$l$的范围内一定有解，所以可以在$O(nlogn)$下求解 | ||
| + | |||
| + | 还有另一种思路是由$T^{(l+1)}=T$，所以$T^{\frac 12}=(T^{\frac 12})^{(l+1)}=T^{\frac{l+1}2}$，记$R=T^{2^s}$，则$T=(R^{\frac{l+1}2})^s$ | ||
2020-2021/teams/wangzai_milk/wzx27/combinatorial_mathematics/permutaitiongroup.1590423831.txt.gz · 最后更改: 2020/05/26 00:23 由 wzx27
