2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 01:47] wzx27 |
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 02:34] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 56: | 行 56: | ||
| 求出置换中所有的循环，考虑每个循环中交换的花费。记某个循环中所有下标对应最小的值为$mi$，循环长度为$len$，该循环中所有下标对应值的和为$sum$，所有序列中的最小值为$low$，则每个循环的最小花费为$$min\{sum+mi\times (len-2),\; sum+mi+low\times (len+1)\}$$ | 求出置换中所有的循环，考虑每个循环中交换的花费。记某个循环中所有下标对应最小的值为$mi$，循环长度为$len$，该循环中所有下标对应值的和为$sum$，所有序列中的最小值为$low$，则每个循环的最小花费为$$min\{sum+mi\times (len-2),\; sum+mi+low\times (len+1)\}$$ | ||
| 其含义为：每个循环中的最小元素分别去交换其他元素使得其他元素在合适位置，或者先让循环内的最小元素和全局的最小元素交换再分别交换循环内的其他元素，结束后重新交换回循环内的最小元素。正确性挺显然的（bushi | 其含义为：每个循环中的最小元素分别去交换其他元素使得其他元素在合适位置，或者先让循环内的最小元素和全局的最小元素交换再分别交换循环内的其他元素，结束后重新交换回循环内的最小元素。正确性挺显然的（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、置换群的幂运算 | 2、置换群的幂运算 | ||
| 行 63: | 行 79: | ||
| 已知$T^{2^s}$求$T$，保证$T$为单循环且长度为奇数 | 已知$T^{2^s}$求$T$，保证$T$为单循环且长度为奇数 | ||
| - | 相当于$T$做了平方运算后，再讲得到的新置换继续平方，一共操作$s$次。因为长度为奇数，所以平方过程中不会分裂，始终保持单循环。再由定理$T^k=\iota$的解是$l$的整数倍，所以如果有$2^t \equiv 1 (\mod l)$，那么$T^{2^t}=T$，即$T^{2^{(t-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)$下求解 | ||
| - | 又$2^t \equiv 1 (\mod 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.1590688025.txt.gz · 最后更改: 2020/05/29 01:47 由 wzx27
