2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 02:22] wzx27 |
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics:permutaitiongroup [2020/05/29 02:34] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 71: | 行 71: | ||
| 有上述定理可知$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)\}$ | 有上述定理可知$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.1590690137.txt.gz · 最后更改: 2020/05/29 02:22 由 wzx27
