题解：P10818 [EC Final 2020] Random Shuffle

· · 题解

不妨设 x 在经过 i 次变换后得到的数值为 f_i，那么显然问题就是变成了给出 n 个同余方程，第 i 个方程的形式为 f_i\equiv X_i\pmod i，其中 X_i 表示第一个循环中与 i 交换的位置。

同时，还是由于涉及到二进制操作，所以可以尝试用暴力的方式。用 bitset 模拟左移和右移的过程，或者不用 bitset 也没问题，就是访问每一位会稍微麻烦一点。这样就可以得到 ```rand()``` 所对应的变换矩阵，可以据此列出异或的线性方程，然后考虑直接搜索或高斯消元。 问题就在于为什么是正确的。注意到对于每个 $i$ 都是可以列出一个方程的，所以实际上解不出来的元只有 $\max\{0,\omega-n+1\}$ 个，注意到高斯消元的复杂度是可以接受的，但是搜索由于限制了 $n$ 的范围，造成搜索的复杂度也不会太高，然后就没问题了。