2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 02:14] wzx27 |
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 02:34] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 64: | 行 64: | ||
| 定义$f[i][j]:=长度为n的所有排列中，最少交换次数为j的排列个数$，于是有$f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-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、置换群的幂运算 | ||
2020-2021/teams/wangzai_milk/wzx27/combinatorial_mathematics/permutaitiongroup.1590689678.txt.gz · 最后更改: 2020/05/29 02:14 由 wzx27
