NC17860. [NOI2014]随机数生成器NOI
描述
小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C++中的 rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。
比如，下面这个二次多项式递推算法就是一个常用算法：
算法选定非负整数 x0,a,b,c,d 作为随机种子，并采用如下递推公式进行计算。
对于任意 i ≥ 1, xi=(a*x[i-1]^2+b*x[i-1]+c)mod d 这样可以得到一个任意长度的非负整数数列{xi},i≥1，一般来说，我们认为这个数列是随机的。
利用随机序列{xi},i≥1，我们还可以采用如下算法来产生一个 1 到 K 的随机排列{Ti},i=1 to k：
1、初始设 T 为 1 到 K 的递增序列；
2、对 T 进行 K 次交换，第 i 次交换，交换 Ti 和 T[xi mod i + 1] 的值。
此外，小 H 在这 K 次交换的基础上，又额外进行了 Q 次交换操作，对于第i 次额外交换，小 H 会选定两个下标 ui 和 vi，并交换 T[ui] 和 T[vi] 的值。
为了检验这个随机排列生成算法的实用性，小 H 设计了如下问题：
小 H 有一个 N 行 M 列的棋盘，她首先按照上述过程，通过 N × M + Q 次交换操作，生成了一个 1~N × M 的随机排列 {Ti},i=1 to N*M，然后将这 N × M 个数逐行逐列依次填入这个棋盘：也就是第 i 行第 i 列的格子上所填入的数应为 T[(i-1)*M+uj]。
接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 N 行第M 列的格子。
小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 N + M − 1 的升序序列，我们称之为路径序列。
小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？
输入描述
第1行包含5个整数，依次为 x_0,a,b,c,d ，描述小H采用的随机数生成算法所需的随机种子。
第2行包含三个整数 N,M,Q ，表示小H希望生成一个1到 N×M 的排列来填入她 N 行 M 列的棋盘，并且小H在初始的 N×M 次交换操作后，又进行了 Q 次额外的交换操作。
接下来 Q 行，第 i 行包含两个整数 u_i,v_i，表示第 i 次额外交换操作将交换 T_(u_i )和 T_(v_i ) 的值
输出描述
输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
示例1
输入:
1 3 5 1 71 3 4 3 1 7 9 9 4 9
输出:
1 2 6 8 9 12
说明:
对于样例 1，根据输入的随机种子，小 H 所得到的前 12 个随机数xi为：C++(clang++ 11.0.1) 解法, 执行用时: 2666ms, 内存消耗: 196176K, 提交时间: 2022-08-28 20:12:56
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5005,inf=1e9;
int d,n,m,q,nm,t1,t2,s[4];
int x[N*N],p[N*N],ll[N],rr[N];
void Add(int &x,int y)
{
x+=y;
if(x>=d) x-=d;
}
bool Able(int o)
{
int x=(o-1)/m+1,y=o%m; if(!y) y=m;
if(y>=ll[x]&&y<=rr[x])
{
for(int i=1;i<x;i++) rr[i]=min(rr[i],y);
for(int i=x+1;i<=n;i++) ll[i]=max(ll[i],y);
return true;
}
return false;
}
int main()
{
scanf("%d%d%d%d%d",&x[0],&s[1],&s[2],&s[3],&d);
scanf("%d%d%d",&n,&m,&q),nm=n*m;
for(int i=1;i<=nm;p[i]=i,i++)
for(int j=3,t=1;j;t=1ll*t*x[i-1]%d,j--)
Add(x[i],1ll*t*s[j]%d);
for(int i=1;i<=nm;i++) swap(p[i],p[x[i]%i+1]);
for(int i=1;i<=q;i++)
scanf("%d%d",&t1,&t2),swap(p[t1],p[t2]);
for(int i=1;i<=n*m;i++) x[p[i]]=i;
for(int i=1;i<=n;i++) ll[i]=1,rr[i]=m;
for(int i=1;i<=nm;i++)
if(Able(x[i])) printf("%d ",i);
return 0;
}