题解：P10818 [EC Final 2020] Random Shuffle

a1a2a3a4a5 · 2025-07-30 16:58:56 · 题解

题意：

求 x，使得以 x 为参数的随机排序可以把排列 1,2,3,4,…,n 排成 a 序列，具体信息看题面的代码。

思路

省选模拟赛这题放在了 T2，可以推断出不是诈骗题，所以我们不得不从代码中推出一些性质：

一

for (int i = 1; i <= n; i++)
{
    a[i] = i;
    swap(a[i], a[rand() % i + 1]);
}

发现这是前缀交换，所以最后一个数只会被交换一次。设 n 在 a_p，那么 \operatorname{rand}\bmod n+1=p，然后再 swap(a[p],a[n])，那么相当于抛去了 n 的影响，现在 n-1 是最后一个数……
我们推出了：

……

二

uint64_t rand()
{
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
}

我们的 x 与 \operatorname{rand} 有关，我们考虑用 x 表示 \operatorname{rand}。
由于 x'=\operatorname{rand}(n) 所以下面我都用 x' 来表示 \operatorname{rand}(n)。

手玩一下左右移异或的性质，为了方便，我们手玩下面这份代码：

uint64_t rand()
{
    x ^= x << 1;
    x ^= x >> 2;
    return x;
}

假设 x_{(2)}=101 （二进制表示）。

结果为 (101\operatorname{xor} 1010)\operatorname{xor} 10=1101，每一位的来源我们可以记录下来，此例：

所以关于 x 的方程组大概是这样的：

综上，我们可以把 x' 的每一位用 x 来表示，然后 x'' 也用 x' 的 x 表示来表示……最终所有式子都化成了初始的 x，这样我们就处理了 x 变化带来的影响并把所有 \operatorname{rand} 值都用 x 表示出来了（\operatorname{rand} 就是上文的 x'、x''）。

三

移项整理上面两个性质，这里写的 x^2 的意思是 x''，而并非次方：

……
我们显然是想解方程似得把 x 解出来，我们性质二的 x' 是依赖二进制位的，所以我们不得不把上面这个式子在二进制上考虑。x 拆成二进制，猜出模数拆成二进制数肯定不劣，我们考虑二进制如何取模？
先分类思考一下，如果模数为 2^x，那么取模相当于保留了后 x 位。在上面式子相当于可以直接求出 x' 后几个二进制位，然后我们可以得到只有 x_i 未知的帅方程。帅方程可以用线性基解，所以我们可以找出 2^x 模数找出他们的帅方程。

但是这样做感觉方程好少啊！

此时宇宙射线横着走过来说：“ 不是，我不是二的整次幂，我直接把多的位数不要了不得了？ 然后我再跟你说：
对于 p=2^xq，(n\bmod p)\equiv n\pmod{2^x}。
证明：