题解：CF444B DZY Loves FFT

dongzirui0817 · 2026-07-21 14:55:16 · 题解

发现输入用了伪随机数，一般是在输入过大时使用。但这题 n\le 10^5，输入大在哪里？

所以说这个输入另有打算。注意到这样输入会使输入随机化，所以考虑人类智慧。

我们发现，随机化数据下，前 100 大的 a_i 很快就会出现。而此时我们可以看 n-99 至 n 这些数。如果有一个数字在 i 前面且对应的 b 为 1，那么它就是答案。

如果找不到怎么办？直接暴力枚举即可。

可以发现，暴力枚举的次数很少，所以可以轻松卡过。

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

int n, d, cnt = 0;
ll x, a[100010], b[100010], p[100010], v[100010];
/*
a, b: 输入数据
p[i]: 第 i 个 b 为 1 的下标
v[i]: i 在 a 中的下标，即 v[a[i]] = i 
*/

ll getNextX(){
    x = (x * 37 + 10007) % 1000000007;
    return x;
}
void initAB(){ 
    for (int i = 0 ; i < n ; i++) a[i] = i + 1;
    for (int i = 0 ; i < n ; i++) swap(a[i], a[getNextX() % (i + 1)]);
    for (int i = 0 ; i < n ; i++)
        if (i < d) b[i] = 1;
        else b[i] = 0;
    for (int i = 0 ; i < n ; i++) swap(b[i], b[getNextX() % (i + 1)]);
}

int main() {
    cin >> n >> d >> x;
    initAB();
    for (int i = 0 ; i < n ; i++) {
        v[a[i]] = i;
        if (b[i]) p[++cnt] = i;
    }
    for (int i = 0 ; i < n ; i++) {
        ll res = 0;
        for (int j = n ; j >= max(1, n - 100) ; j--)    // 看前 100 大 
            if (i >= v[j] && b[i - v[j]]) {
                res = j;
                break;
            }
        if (!res) {     // 没找到就暴力枚举 
            for (int j = 1 ; j <= cnt && i >= p[j] ; j++)
                res = max(res, a[i - p[j]]);
        }
        cout << res << endl;
    }
    return 0;
}