#P18744. [正睿NOI2021训练] 第六题

[正睿NOI2021训练] 第六题

第六题

下面的程序使用线性同余随机数生成器,将排列 [1,2,…,n][1,2,\ldots,n] 打乱:

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]。

现在给出 n,a,b,pn,a,b,p 和程序最后输出的排列 permperm,求运行程序之前的初始种子 xx。

这是一道普通输入输出的种子恢复题,不是交互题。若有多个合法种子,输出任意一个能完整生成给定排列的种子即可。

输入格式

第一行一个整数 nn。

第二行 nn 个整数,表示输出的排列 perm1,…,permnperm_1,\ldots,perm_n。

第三行三个整数 a,b,pa,b,p。保证 pp 是素数。

输出格式

输出一个整数 xx,满足 0≤x<p0\le x<p,且以上程序以此为初始种子时,生成的完整排列与输入相同。

数据范围

n=105n=10^5,500≤p≤1016500\le p\le10^{16},2≤a<p2\le a<p,0≤b<p0\le b<p。保证存在合法种子。

原题规定 b,xb,x 在 [0,p−1][0,p-1] 中随机产生;除小乘数专用数据外,aa 在 [2,p−1][2,p-1] 中随机产生,小乘数数据的 aa 在 [2,200][2,200] 中随机产生。

完整样例

由于原题固定 n=100000n=100000,使用附件给出完整样例:样例输入、一个合法输出。

样例输出仅为一种可行答案,评测检查种子实际生成的排列。