3757. 【NOI2014】随机数生成器

Description

Input

输入文件的第 1 行包含 5 个整数，依次为 x0, a, b, c, d，描述小 H 采用的随机数生成算法所需的随机种子。

第 2 行包含三个整数 N, M, Q，表示小 H 希望生成一个 1 到 N × M 的排列来填入她 N 行 M 列的棋盘，并且小 H 在初始的 N × M 次交换操作后，又进行了 Q 次额外的交换操作。

接下来 Q 行，第 i 行包含两个整数 ui, vi，表示第 i 次额外交换操作将交换 T_ui 和 T_vi 的值。

Output

输出一行，包含 N + M − 1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。

Sample Input

【样例输入 1】

1 3 5 1 71

3 4 3

1 7

9 9

4 9

【样例输入 2】

654321 209 111 23 70000001

10 10 0

【样例输入 3】

123456 137 701 101 10000007

20 20 0

 

Sample Output

【样例输出 1】

1 2 6 8 9 12

【样例输出 2】

1 3 7 10 14 15 16 21 23 30 44 52 55 70 72 88 94 95 97

【样例输出 3】

1 10 12 14 16 26 32 38 44 46 61 81 84 101 126 128 135 140 152 156 201 206 237 242 243 253 259 269 278 279 291 298 338 345 347 352 354 383 395

 

Data Constraint

Hint

【样例说明】

对于样例 1，根据输入的随机种子，小 H 所得到的前 12 个随机数xi 为：

9 5 30 11 64 42 36 22 1 9 5 30

根据这 12 个随机数，小 H 在进行初始的 12 次交换操作后得到的排列为： 

6 9 1 4 5 11 12 2 7 10 3 8

在进行额外的 3 次交换操作之后，小 H 得到的最终的随机排列为：

12 9 1 7 5 11 6 2 4 10 3 8

这个随机排列可以得到如下的棋盘：

12  9  1  7

5  11  6  2

4  10  3  8 

最 优 路 径 依 次 经 过 的 数 字 为 ：

12->9->1->6->2->8。

对于样例 3，由于卷面宽度不够，在样例输出中出现了换行。请注意，这里的换行仅作展示用途，事实上， 样例输出有且仅有一行，所有的数字都应该出现在同一行中。

【特别提示】

本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。

一个 32 位整数（例如 C/C++中的 int 和 Pascal 中的 Longint）为 4 字节，因而如果在程序中声明一个长度为 1024 × 1024 的 32 位整型变量的数组，将会占用 4 MB 的内存空间。

Solution

按题意模拟出数列（可以不用矩阵），直接在数列中进行转换即可。设left[i],righ[i]分别表示矩阵中第i行从left[i]-right[i]这个区间都是可以选择的数，那么我们从小到大枚举数，如果能在所选范围中就选，选完后将当前点上面所有的行的right与当前的列取min，以及下面的行的left与这个点所在的列取max就可以了，因为选择了一个点后，它左下角和右上角的一个矩阵就不能选择。

当然也可以用并查集来做。

Code

#include<cstdio> 
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(register I i=a;i<=b;++i)
#define Fd(i,a,b) for(register I i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define N 5001
using namespace std;
I a,b,c,d,n,m,q,x[N*N],t[N*N],lf[N],rg[N],ans[N<<1];
void rd(I &x){
	x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
I main(){
	rd(x[0]),rd(a),rd(b),rd(c),rd(d);
	rd(n),rd(m),rd(q);
	F(i,1,n*m) x[t[i]=i]=(((ll)x[i-1]*x[i-1]%d*(ll)a%d+(ll)b*x[i-1])%d+(ll)c)%d;
	F(i,1,n*m) swap(t[i],t[x[i]%i+1]);
	while(q--){
		rd(a),rd(b);
		swap(t[a],t[b]);
	}
	F(i,1,n){
		F(j,1,m) x[t[(i-1)*m+j]]=(i-1)*m+j;
		lf[i]=1,rg[i]=m;
	}
	lf[1]++,rg[n]--;
	ans[1]=t[1],ans[ans[0]=2]=t[n*m];
	F(i,1,n*m) if(x[i]!=1&&x[i]!=n*m){
		I x1=(x[i]-1)/m+1,y1=x[i]-(x1-1)*m;
		if(y1<lf[x1]||y1>rg[x1]) continue;
		ans[++ans[0]]=t[x[i]];
		F(j,1,x1-1) rg[j]=min(rg[j],y1);
		F(j,x1+1,n) lf[j]=max(lf[j],y1);
	}
	sort(ans+1,ans+1+ans[0]);
	F(i,1,ans[0]) printf("%d ",ans[i]);
	return 0;
}