Readme

1806.Minimum-Number-of-Operations-to-Reinitialize-a-Permutation

本题的操作是：将数组的前半部分元素重新分配到偶数位（index=0,2,4,6...），将数组的后半部分元素重新分配到奇数位（index=1,3,5,7...）。

解法1：

模拟整个过程，判断新生成的数组是否与初始数组完全相同。

解法2：

在充分理解了变换的本质之后，我们可以写出某个位置i上的数字在一次变化之后的新位置f(i)

if i<N/2, f(i) = i*2
if N/2<=i<N, f(i) = i*2 - (N-1)

假设n=10. 我们如果追踪数字1（初始的index是1），那么第二个回合这个1就移动到了数组的第2个位置. 第三个回合这个1移动了第4个位置，如此重复，当index第二次变成1的时候，就是一个周期。

01234567
04152637
02461357
01234567
04152637
02461357
01234567

但是这个方法是有缺陷的，即为什么一定要追踪数字1？如果你选择数字3的话，你就会发现你追踪到的周期是2，但整个数组变化的周期是6.

解法3：

我们将之前的变化公式可以统一为：f(i) = 2*i mod (N-1)

假设连续操作k次，得到f^k(i) = 2^k * i mod (N-1). 如果操作k次得到初始的状态，也就是f^k(i)=i，那么即有2^k * i ≡ i (mod N-1)。为了使这个式子对于任意的i恒成立，必须2^k能够被(N-1)整除余1. 所以我们只需要将k从1往上不断尝试即可。

需要注意的是，当k大于32时，2^k就已经超出了整形范围。所以我们每次将power再乘以2时，需要对(N-1)取余降低数值的大小，同时也不影响最终的结果。这是因为 x ≡ x % m (mod m)