解题思路
本题要求构造一个排列 p,满足对于任意 1≤i≤n 都有 ppi=n−i+1。通过分析条件可以得出,只有当 n 除以 4 余 0 或余 1 时才有解,否则输出 −1。
原因:将等式两边再次应用条件可以得到 pi 与索引之间的关系,经推导和尝试可知,当 nmod4=2 或 nmod4=3 时,无法形成合法的闭环映射,而 nmod4=0 或 1 时存在构造方案。
构造方法如下(使用 1 为起始索引):
- 从 i=1 开始,每次增加 2,直到 i≤⌊n/2⌋。对于每一个 i,同时设置四个位置的值: