2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2 [2020/08/07 10:15] potassium J?K |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-2 [2020/08/15 18:05] (当前版本) nikkukun add J |
||
|---|---|---|---|
| 行 130: | 行 130: | ||
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | 给一个长度 $n \leq 10^5$ 的置换 $A$ 和一个大质数 $k \in [10^8, 10^9]$，求是否存在另一个置换 $P$ 使得 $P^k = A$。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | 考虑 $P$ 轮换乘积形式中的每个轮换，其 $k$ 次方相当于轮换移动了 $k$ 次。由于 $k$ 是个大质数，其必然与轮换长度互质，故轮换操作不会改变轮换长度（不互质的情况可能会让一个轮换变成很多小轮换），直接将 $A$ 中的每个轮换倒着移动 $k$ 次即可还原。 | ||
| + | |||
| + | 总时间复杂度 $O(n)$。 | ||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-2.1596766520.txt.gz · 最后更改: 2020/08/07 10:15 由 potassium
