随机数生成器
【问题描述】
小H最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如Pascal中的random和C/C++中的rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。比如，下面这个二次多项式递推算法就是一个常用算法：算法选定非负整数 x0,a,b,c,d 作为随机种子，并采用如下递推公式进行计算。对于任意 i≥1,
这样可以得到一个任意长度的非负整数数列{xi }(i≥1)，一般来说，我们认为这个数列是随机的。利用随机序列{xi }(i≥1)，我们还可以采用如下算法来产生一个1到K的随机排列{Ti }(i=1)K：初始设T为1到K的递增序列；对T进行K次交换，第 i 次交换，交换 Ti 和 T((x(i) mod i)+1) 的值。此外，小H在这 K 次交换的基础上，又额外进行了 Q 次交换操作，对于第 i 次额外交换，小H会选定两个下标 ui 和 vi，并交换 T(u_i ) 和 T(v_i ) 的值。为了检验这个随机排列生成算法的实用性，小H设计了如下问题：小H有一个 N 行 M 列的棋盘，她首先按照上述过程，通过 N×M+Q 次交换操作，生成了一个 1~N×M 的随机排列 {Ti }(i=1)(N×M)，然后将这 N×M 个数逐行逐列依次填入这个棋盘：也就是第 i 行第 j 列的格子上所填入的数应为 T((i-1)●M+j)。接着小H希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 N 行第 M 列的格子。小H把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小H都可以得到一个长度为 N+M-1 的升序序列，我们称之为路径序列。小H想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？
【数据规模与约定】
所有测试数据的范围和特点如下表所示：
测试点编号 N,M 的规模 Q 的规模 约定
1 2≤N,M≤ 8 Q=0 0≤a≤3000≤b,c≤1080≤x0<d≤1081≤ui,vi≤N×M
2 2≤N,M≤200
3
4 2≤N,M≤2000 0≤Q≤50000
5
6
7 2≤N,M≤5000
8
9
10
【特别提示】
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
【输入形式】
从文件random.in中读入数据。 输入文件的第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 ) 的值。
【输出形式】
输出到文件random.out中。 输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
【输入样例1】
1 3 5 1 71
3 4 3
1 7
9 9
4 9
【输出样例1】
1 2 6 8 9 12
【输入样例2】
654321 209 111 23 70000001
10 10 0
【输出样例2】
1 3 7 10 14 15 16 21 23 30 44 52 55 70 72 88 94 95 97
【输入样例3】
123456 137 701 101 10000007
20 20 0
【输出样例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
【样例说明】
对于样例1，根据输入的随机种子，小H所得到的前12个随机数x_i为：
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→6→2→8。
对于样例3，由于卷面宽度不够，在样例输出中出现了换行。请注意，这里的换行仅作展示用途，事实上，样例输出有且仅有一行，所有的数字都应该出现在同一行中。
【样例输入输出4】
参见：random.zip
【时间限制】
5s
【空间限制】
256000KB
【上传文件】
上传c, cpp, pas语言源程序，文件名为random.c, random.cpp, random.pas。
题解：
考场上没时间了，写了个暴力找最小+分治都没调出来，不过确实有点慌了。。。
正解是直接从1 到 N*M枚举，如果该点可以被走，那么就一定要走这个点，那么他的左下和右上就不能走，暴力标记为不能走。。。
神做法，好巧妙的说。。。
接下来考虑如何减少暴力的复杂度，有些店可能背删了好多次，因此我们考虑，当我们在标记的时候，碰到了一个点他已经被标记过了，这时候该怎么办
不妨设我们正在标记 x 左下方的点，发现 y 已经被标记过，那么：
1.y 第一次被标记的时候一定是处于某个点的左下方，被打了标记，因为如果是右上方那么 x 应该也被做了标记
2.这样的话处于y左方，下方，以及右下方的一定也被标记过了，我们可以不用标记了，需要做标记的范围可以缩小
实现的话我们可以不用用两个变量来表示需要做标记的边界
可以这样做
1.在内循环里只要碰到标记过的点就break
2.在外循环里如果发现内循环break的时后只循环到了最开始要做标记的边界的时候，外层break
但要注意边界的情况
还有一种做法，是hzwer大神的，用 l，r 数组表示每一行当前没被标记的点的区间，这是因为考虑到每时每刻每一行中可行区域都是连续的，
因此更新的时候，只要维护边界，取min max就行了
代码：
1.考场 0分（我还以为会CE了呢。。。）
1 var x,y:array[0..2500000] of int64; 2 a,b,c,d:int64; 3 num,ans:array[0..50000] of longint; 4 i,j,n,m,q,t,xx,yy,tot,cnt:longint; 5 heng,zong:array[0..2500000] of longint; 6 can:array[0..2500000] of boolean; 7 function min(x,y:longint):longint; 8 begin 9 if x<y then exit(x) else exit(y); 10 end; 11 procedure init; 12 begin 13 readln(x[0],a,b,c,d); 14 readln(n,m,q); 15 for i:=1 to n*m do x[i]:=((a*((x[i-1]*x[i-1]) mod d) mod d)+(b*x[i-1] mod d+c)) mod d; 16 for i:=1 to n*m do y[i]:=i; 17 for i:=1 to n*m do 18 begin 19 j:=x[i] mod i+1; 20 t:=y[i];y[i]:=y[j];y[j]:=t; 21 end; 22 for i:=1 to q do 23 begin 24 readln(xx,yy); 25 t:=y[xx];y[xx]:=y[yy];y[yy]:=t; 26 end; 27 for i:=1 to n*m do num[y[i]]:=i; 28 for i:=1 to n*m do begin heng[i]:=(i-1) div m+1;zong[i]:=(i-1) mod m+1;end; 29 end; 30 function check(x,y:longint):boolean; 31 begin 32 if heng[num[x]]>heng[num[y]] then exit(false); 33 if zong[num[x]]>zong[num[y]] then exit(false); 34 exit(true); 35 end; 36 function dfs(x1,y1,x2,y2:longint):longint; 37 var i,j:longint; 38 begin 39 dfs:=maxlongint; 40 for i:=x1 to x2 do 41 for j:=y1 to y2 do 42 if ((i=x1) and (j=y1)) or ((i=x2) and (j=y2)) then continue 43 else dfs:=min(dfs,y[(i-1)*m+j]); 44 end; 45 procedure update(x1,y1,x2,y2:longint); 46 var tmp:longint; 47 begin 48 if abs(x1-x2)+abs(y1-y2)<=1 then exit; 49 tmp:=dfs(x1,y1,x2,y2);if tmp=maxlongint then exit; 50 can[tmp]:=true; 51 update(x1,y1,heng[tmp],zong[tmp]); 52 update(heng[tmp],zong[tmp],x2,y2); 53 end; 54 procedure main; 55 begin 56 tot:=1; 57 ans[1]:=y[1];if y[1]<>1 then begin inc(tot);ans[2]:=1;end; 58 for i:=tot+1 to n+m-1 do 59 begin 60 j:=ans[i-1]+1; 61 while not(check(ans[i-1],j)) do inc(j); 62 ans[i]:=j; 63 if num[j]=n*m then break; 64 end; 65 tot:=i; 66 for i:=1 to tot do can[ans[i]]:=true; 67 for i:=1 to tot-1 do 68 update(heng[num[ans[i]]],zong[num[ans[i]]],heng[num[ans[i+1]]],zong[num[ans[i+1]]]); 69 cnt:=0; 70 for i:=1 to n*m do if can[i] then begin inc(cnt);if cnt=n+m-1 then break;write(i,‘ ‘);end; 71 writeln(i); 72 end; 73 begin 74 assign(input,‘random.in‘);assign(output,‘random.out‘); 75 reset(input);rewrite(output); 76 init; 77 main; 78 close(input);close(output); 79 end. 80
2.筛法没有处理边界 80分
1 const maxn=5000*5000+10; 2 var x,y:array[0..maxn] of longint; 3 a,b,c,d,x0,x1:int64; 4 i,j,k,n,m,t,q,xx,yy,cnt:longint; 5 check:array[0..maxn] of boolean; 6 flag:boolean; 7 function min(x,y:longint):longint; 8 begin 9 if x<y then exit(x) else exit(y); 10 end; 11 procedure init; 12 begin 13 readln(x0,a,b,c,d); 14 readln(n,m,q); 15 for i:=1 to n*m do 16 begin 17 x1:=(x0*(a*x0+b)+c) mod d; 18 x0:=x1; 19 x[i]:=x1; 20 end; 21 for i:=1 to n*m do y[i]:=i; 22 for i:=1 to n*m do 23 begin 24 j:=x[i] mod i+1; 25 t:=y[i];y[i]:=y[j];y[j]:=t; 26 end; 27 for i:=1 to q do 28 begin 29 readln(xx,yy); 30 t:=y[xx];y[xx]:=y[yy];y[yy]:=t; 31 end; 32 for i:=1 to n*m do x[y[i]]:=i; 33 end; 34 procedure main; 35 begin 36 fillchar(check,sizeof(check),false); 37 cnt:=0; 38 for i:=1 to n*m do 39 begin 40 if check[i] then continue; 41 inc(cnt);if cnt<>n+m-1 then write(i,‘ ‘) else begin writeln(i);break;end; 42 xx:=(x[i]-1) div m+1;yy:=(x[i]-1) mod m+1;//writeln(i,‘ ‘,x[i],‘ ‘,xx,‘ ‘,yy); 43 for j:=xx-1 downto 1 do 44 begin 45 for k:=yy+1 to m do 46 if check[y[(j-1)*m+k]] then begin break;end 47 else check[y[(j-1)*m+k]]:=true; 48 if k=yy+1 then break; 49 end; 50 for j:=xx+1 to n do 51 begin 52 for k:=yy-1 downto 1 do 53 if check[y[(j-1)*m+k]] then begin break;end 54 else check[y[(j-1)*m+k]]:=true; 55 if k=yy-1 then break; 56 end; 57 end; 58 //for i:=1 to n*m do writeln(check[i],‘ ‘,y[i]); 59 end; 60 61 begin 62 assign(input,‘random.in‘);assign(output,‘random.out‘); 63 reset(input);rewrite(output); 64 init; 65 main; 66 close(input);close(output); 67 end. 68 69
3.筛法考虑边界 100分
1 const maxn=5000*5000+10; 2 var x,y:array[0..maxn] of longint; 3 a,b,c,d,x0,x1:int64; 4 i,j,k,n,m,t,q,xx,yy,cnt:longint; 5 check:array[0..maxn] of boolean; 6 flag:boolean; 7 function min(x,y:longint):longint; 8 begin 9 if x<y then exit(x) else exit(y); 10 end; 11 procedure init; 12 begin 13 readln(x0,a,b,c,d); 14 readln(n,m,q); 15 for i:=1 to n*m do 16 begin 17 x1:=(x0*(a*x0+b)+c) mod d; 18 x0:=x1; 19 x[i]:=x1; 20 end; 21 for i:=1 to n*m do y[i]:=i; 22 for i:=1 to n*m do 23 begin 24 j:=x[i] mod i+1; 25 t:=y[i];y[i]:=y[j];y[j]:=t; 26 end; 27 for i:=1 to q do 28 begin 29 readln(xx,yy); 30 t:=y[xx];y[xx]:=y[yy];y[yy]:=t; 31 end; 32 for i:=1 to n*m do x[y[i]]:=i; 33 end; 34 procedure main; 35 begin 36 fillchar(check,sizeof(check),false); 37 cnt:=0; 38 for i:=1 to n*m do 39 begin 40 if check[i] then continue; 41 inc(cnt);if cnt<>n+m-1 then write(i,‘ ‘) else begin writeln(i);break;end; 42 xx:=(x[i]-1) div m+1;yy:=(x[i]-1) mod m+1;//writeln(i,‘ ‘,x[i],‘ ‘,xx,‘ ‘,yy); 43 for j:=xx-1 downto 1 do 44 begin 45 for k:=yy+1 to m do 46 if check[y[(j-1)*m+k]] then begin break;end 47 else check[y[(j-1)*m+k]]:=true; 48 if (k=yy+1) and (k<>m) then break; 49 end; 50 for j:=xx+1 to n do 51 begin 52 for k:=yy-1 downto 1 do 53 if check[y[(j-1)*m+k]] then begin break;end 54 else check[y[(j-1)*m+k]]:=true; 55 if (k=yy-1) and (k<>1) then break; 56 end; 57 end; 58 //for i:=1 to n*m do writeln(check[i],‘ ‘,y[i]); 59 end; 60 61 begin 62 assign(input,‘random.in‘);assign(output,‘random.out‘); 63 reset(input);rewrite(output); 64 init; 65 main; 66 close(input);close(output); 67 end. 68
4.l，r数组维护区间 100分
1 const maxn=5000*5000+10; 2 var x,y:array[0..maxn] of longint; 3 a,b,c,d,x0,x1:int64; 4 i,j,k,n,m,t,q,xx,yy,cnt:longint; 5 l,r:array[0..5005] of longint; 6 flag:boolean; 7 function min(x,y:longint):longint; 8 begin 9 if x<y then exit(x) else exit(y); 10 end; 11 function max(x,y:longint):longint; 12 begin 13 if x>y then exit(x) else exit(y); 14 end; 15 procedure init; 16 begin 17 readln(x0,a,b,c,d); 18 readln(n,m,q); 19 for i:=1 to n*m do 20 begin 21 x1:=(x0*(a*x0+b)+c) mod d; 22 x0:=x1; 23 x[i]:=x1; 24 y[i]:=i; 25 end; 26 for i:=1 to n*m do 27 begin 28 j:=x[i] mod i+1; 29 t:=y[i];y[i]:=y[j];y[j]:=t; 30 end; 31 for i:=1 to q do 32 begin 33 readln(xx,yy); 34 t:=y[xx];y[xx]:=y[yy];y[yy]:=t; 35 end; 36 for i:=1 to n*m do x[y[i]]:=i; 37 end; 38 procedure main; 39 begin 40 cnt:=0; 41 for i:=1 to n do begin l[i]:=1;r[i]:=m;end; 42 for i:=1 to n*m do 43 begin 44 xx:=(x[i]-1) div m+1;yy:=(x[i]-1) mod m+1;//writeln(i,‘ ‘,x[i],‘ ‘,xx,‘ ‘,yy); 45 if (yy<=r[xx]) and (yy>=l[xx]) then 46 begin 47 for j:=1 to n do 48 if j<xx then r[j]:=min(yy,r[j]) 49 else if j>xx then l[j]:=max(yy,l[j]); 50 inc(cnt);if cnt<>n+m-1 then write(i,‘ ‘) else begin writeln(i);break;end; 51 end; 52 end; 53 //for i:=1 to n*m do writeln(check[i],‘ ‘,y[i]); 54 end; 55 56 begin 57 assign(input,‘random.in‘);assign(output,‘random.out‘); 58 reset(input);rewrite(output); 59 init; 60 main; 61 close(input);close(output); 62 end.
原文：http://www.cnblogs.com/zyfzyf/p/3888051.html
