对于哪些n,存在一个1到n-1的排列S_1, S_2, …, S_n-1,使得T_1, T_2, …, T_n-1也是一个1到n-1的排列,其中,
T_1 = S_1 mod n,
T_2 = (S_1 + S_2) mod n,
T_3 = (S_1 + S_2 + S_3) mod n,
…….
T_n-1 = (S_1 + S_2 + … + S_n-1) mod n.
首先,当n为奇数时,这样的排列永远不可能出现,因为T_n-1 = (1 + 2 + … + (n-1)) mod n = 0,而我们的排列是不包含0的。
当n为偶数时,这样的排列是一定存在的。事实上,当n为偶数时,n-1, 2, n-3, 4, n-5, 6, …, 3, n-2, 1就是一个合法的解。比如说,当n=10时,9, 2, 7, 4, 5, 6, 3, 8, 1就是一个解。
为什么这一定是一个满足题目要求的解呢?因为,它们除以n的余数分别是-1, 2, -3, 4, -5, 6, …,其前缀和恰为-1, +1, -2, +2, -3, +3, …。