#P18744. [正睿NOI2021训练] 第六题
[正睿NOI2021训练] 第六题
第六题
下面的程序使用线性同余随机数生成器,将排列 打乱:
long long x, a, b, p;
long long next_random() {
x = ((__int128)x * a + b) % p;
return x;
}
// 先读入 n、初始 x、a、b、p。
for (int i = 1; i <= n; ++i) {
perm[i] = i;
swap(perm[i], perm[next_random() % i + 1]);
}
// 输出 perm[1], ..., perm[n]。
现在给出 和程序最后输出的排列 ,求运行程序之前的初始种子 。
这是一道普通输入输出的种子恢复题,不是交互题。若有多个合法种子,输出任意一个能完整生成给定排列的种子即可。
输入格式
第一行一个整数 。
第二行 个整数,表示输出的排列 。
第三行三个整数 。保证 是素数。
输出格式
输出一个整数 ,满足 ,且以上程序以此为初始种子时,生成的完整排列与输入相同。
数据范围
,,,。保证存在合法种子。
原题规定 在 中随机产生;除小乘数专用数据外, 在 中随机产生,小乘数数据的 在 中随机产生。
完整样例
由于原题固定 ,使用附件给出完整样例:样例输入、一个合法输出。
样例输出仅为一种可行答案,评测检查种子实际生成的排列。