题解：P10818 [EC Final 2020] Random Shuffle

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

$X_i$ 是容易线性求解的，那么问题就在于 $f_i$。如果是一般的问题的话，肯定是考虑把 $f_i$ 表示成关于 $x$ 的多项式函数。但是这里涉及到二进制操作，所以不太能表示成多项式函数。

同时，还是由于涉及到二进制操作，所以可以尝试用暴力的方式。用 bitset 模拟左移和右移的过程，或者不用 bitset 也没问题，就是访问每一位会稍微麻烦一点。这样就可以得到 rand() 所对应的变换矩阵，可以据此列出异或的线性方程，然后考虑直接搜索或高斯消元。

问题就在于为什么是正确的。注意到对于每个 $i$ 都是可以列出一个方程的，所以实际上解不出来的元只有 $\max\{0,\omega-n+1\}$ 个，注意到高斯消元的复杂度是可以接受的，但是搜索由于限制了 $n$ 的范围，造成搜索的复杂度也不会太高，然后就没问题了。