#P18638. Linear Congruential Generator Problem

Linear Congruential Generator Problem

Linear Congruential Generator Problem

考虑下面用来生成伪随机排列的 C++ 程序:

long long x, a, b, p;
int n;
int perm[100001];

long long rand() {
    x = ((__int128)x * a + b) % p;
    return x;
}

int main() {
    cin >> n;
    cin >> x >> a >> b >> p;
    for (int i = 1; i <= n; i++) {
        perm[i] = i;
        swap(perm[i], perm[rand() % i + 1]);
    }
    for (int i = 1; i <= n; i++) {
        cout << perm[i] << (i == n ? '\n' : ' ');
    }
}

给定 n,a,b,pn,a,b,p 以及这段程序输出的排列 perm1,…,permn\mathrm{perm}_1,\ldots,\mathrm{perm}_n,请找出一个可能的初始值 xx,满足 0≤x<p0\le x<p。

每次调用随机数函数时,会先更新 xx,再用更新后的值决定本次交换位置。你需要输出的是进入整个生成过程之前的初始值。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 perm1,…,permn\mathrm{perm}_1,\ldots,\mathrm{perm}_n,构成 1,…,n1,\ldots,n 的一个排列。

第三行三个整数 a,b,pa,b,p。

输出格式

输出一个整数 xx,满足 0≤x<p0\le x<p,使给定参数和该初始值通过上述程序产生输入中的完整排列。

如果有多个解,输出任意一个即可。

数据范围与生成保证

  • n=105n=10^5,这里 nn 是固定值;
  • 1≤permi≤n1\le\mathrm{perm}_i\le n,每个值恰好出现一次;
  • 500≤p≤1016500\le p\le10^{16},且 pp 是素数;
  • 2≤a<p2\le a<p,0≤b<p0\le b<p;
  • a,ba,b 和原初始值 xx 分别从各自的合法范围中均匀随机、独立选择;
  • 输入排列由上述过程生成,因此保证存在合法解。

输入只有一组数据。

样例输入 1(节选)

本例包含 100000100000 个排列元素。下面与原题一样只展示节选,省略号不是实际输入内容。可下载[完整样例输入](file://sample_input.txt)用于运行程序。

100000
38898 35776 38192 80605 84959 ...
356846063 184710711 911417497

样例输出 1

681779867

[完整样例输出附件](file://sample_output.txt)。