[Medium-Hard] P10818 [EC Final 2020] Random Shuffle

简要题意

给定 $n$ 和随机数种子 $x$，下述代码可以生成一个长度为 $n$ 的随机排列。

auto generate(int n, uint64_t x){
    auto next = [&x](){
        x ^= x << 13, x ^= x >> 7, x ^= x << 17;
        return x;
    };
    vector<int> ret(n + 1);
    iota(ret.begin(), ret.end(), 0);
    for(int i=1;i<=n;i++) swap(ret[i], ret[next() % i + 1]);
    return ret;
}

现在给定 $n$ 和一个排列 $p$，求任意一个可以生成它的随机数种子。

$50\leq n\leq 10^5$。保证存在种子 $x\in[0,2^{64})$。

思路

这道题有点强。

首先我们考虑还原每次随机生成的数，这是容易的，倒序枚举 $i$，则 $p_i$ 和 $p_j=i$ 间必有交换。于是可以求得 $f(x)=\mathrm{next}()\bmod x$ 为每次随机数对次序取模后的值。

由于随机数生成是基于 xor-shift 算法的，所以我们可以逐位考虑，然后立即可得每一位都是由初始种子 $x$ 的若干位异或得到（这个同样是可以简单维护的），因此对于每一位，就可以看成一个异或方程，自然想到高斯消元法解异或方程组，所以现在我们的核心任务是将做法往异或方程上套。

观察到这个取模非常难搞，不过如果 $i$ 为 $2$ 的自然数次幂的话，$f(i)$ 是有意义的，它就是 $\mathrm{next}()$ 的后若干位，可以贡献等量的方程。

不过这点方程仍然不够，我们需要更多的方程。

真的只有模数为 $2$ 的整数次幂的模数才有用吗？答案是否定的。假如模数为 $6=(110)_2$，我们能得到什么信息？

观察到如果存在 $2^0$ 进制位，那么与 $6$ 的余数也存在 $2^0$，反之亦然。这是容易证明的。

将结论一般化，我们需要证明的是这样一个结论：

对于 $p=2^xq$，则 $(n\bmod p) \equiv n\pmod{2^x}$。

证明：取 $n$ 同余分解 $n=kp+r=kq2^x+r$。则 $n-r\equiv{0}\pmod{2^x}$，故原命题得证。

所以对于 $f(x)$，只需要将 $x$ 分解为 $2^ab$，就可以得到 $a$ 个方程，分别对应 $f(x)$ 的位 $[1,a]$。

于是我们可以得到的方程大为增加，不过我们只需要保留 $64$ 个，因为 $x$ 最多 $64$ 位，不足的话用空方程补齐。

然后解这个方程，大概率无法得到解，会有若干个自由元无法确定。经过实践，大约最多 $17$ 个，而 $2^{17}$ 是一个枚举可以接受的范围，所以暴力枚举自由元，将其他元推算出来，检验是否合法即可。

代码

考试上写的，有点混乱，建议别学。

#include <bits/stdc++.h>
using namespace std;

using ui64 = unsigned long long;

const int N = 1e5 + 5;
int n, a[N], pos[N], rnd[N];
bitset<64> bs[65], eq[65];
ui64 ret[65];
bool vis[65], answer[N];
int in_free[65];

ui64 next_rnd(ui64 &x){
    x ^= (x << 13);
    x ^= (x >> 7);
    x ^= (x << 17);
    return x;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i], pos[a[i]] = i;
    for(int i=n;i;i--){
        rnd[i] = pos[i];
        swap(a[i], a[rnd[i]]);
        pos[a[rnd[i]]] = rnd[i];
        rnd[i]--;
    }
    int tot = 0;
    for(int i=0;i<64;i++) bs[i][i] = 1;
    for(int i=1;i<=n;i++){
        // x ^= (x << 13);
        for(int j=63;j>=13;j--) bs[j] ^= bs[j - 13];
        // x ^= (x >> 7);
        for(int j=0;j<64-7;j++) bs[j] ^= bs[j + 7];
        // x ^= (x << 17);
        for(int j=63;j>=17;j--) bs[j] ^= bs[j - 17];
        for(int j=1;j<64;j++){
            if(i % (1ull << j)) continue;
            eq[++tot] = bs[j - 1], ret[tot] = (rnd[i] >> (j - 1)) & 1;
            if(tot == 64) break;
        }
        if(tot == 64) break;
    }
    vector<int> free;
    for(int i=0;i<64;i++){
        int pos = -1;
        for(int j=1;j<=64;j++){
            if(eq[j][i] && !vis[j]){
                pos = j, vis[pos] = 1;
                break;
            }
        }
        if(!(~pos)){
            free.push_back(i);
            continue;
        }
        for(int j=1;j<=64;j++){
            if(j == pos || !eq[j][i]) continue;
            eq[j] ^= eq[pos], ret[j] ^= ret[pos];
        }
    }
    int t = free.size();
    // cerr << t << '\n';
    tot = 0; ui64 S = 0;
    for(int i : free) in_free[i] = tot++, S |= (1ull << i);
    for(int i=0;i<(1<<t);i++){
        ui64 x = 0;
        for(int k=0;k<64;k++){
            if(S & (1ull << k)) x ^= (ui64)((i >> in_free[k]) & 1) << k;
        }
        for(int j=1;j<=64;j++){
            int pos = -1;
            bool tmp = 0;
            for(int k=0;k<64;k++){
                if(S & (1ull << k)) tmp ^= ((i >> in_free[k]) & 1) & eq[j][k];
                else if(eq[j][k]) pos = k;
            }
            tmp ^= ret[j];
            if(!(~pos)) continue;
            if(tmp) x |= (1ull << pos);
        }
        ui64 bak = x;
        bool flag = 0;
        for(int j=1;j<=n;j++){
            if((next_rnd(x) % j) != rnd[j]){
                flag = 1;
                break;
            }
        }
        if(!flag){
            cout << bak << '\n';
            return;
        }
    }
    // cout << "no solution\n";
}

void clear(){
    for(int i=0;i<=64;i++){
        bs[i].reset(), eq[i].reset();
        ret[i] = vis[i] = answer[i] = in_free[i] = 0;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--) solve(), clear();
    return 0;
}

// Written by xiezheyuan