#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' : ' ');
}
}
给定 以及这段程序输出的排列 ,请找出一个可能的初始值 ,满足 。
每次调用随机数函数时,会先更新 ,再用更新后的值决定本次交换位置。你需要输出的是进入整个生成过程之前的初始值。
输入格式
第一行一个整数 。
第二行 个整数 ,构成 的一个排列。
第三行三个整数 。
输出格式
输出一个整数 ,满足 ,使给定参数和该初始值通过上述程序产生输入中的完整排列。
如果有多个解,输出任意一个即可。
数据范围与生成保证
- ,这里 是固定值;
- ,每个值恰好出现一次;
- ,且 是素数;
- ,;
- 和原初始值 分别从各自的合法范围中均匀随机、独立选择;
- 输入排列由上述过程生成,因此保证存在合法解。
输入只有一组数据。
样例输入 1(节选)
本例包含 个排列元素。下面与原题一样只展示节选,省略号不是实际输入内容。可下载[完整样例输入](file://sample_input.txt)用于运行程序。
100000
38898 35776 38192 80605 84959 ...
356846063 184710711 911417497
样例输出 1
681779867
[完整样例输出附件](file://sample_output.txt)。