「LOJ 2248」「NOI2014」随机数生成器

发表于

小 H 有一个 NN 行 MM 列的棋盘，她首先按照上述过程，通过 N×M+QN\times M+Q 次交换操作，生成一个 1∼N×M1 \sim N \times M 的随机排列 {Ti}i≥1N×M\{T_i\}^{N \times M}_{i \geq 1} ，然后将这 N×MN \times M 个数逐行逐列依次填入这个棋盘：也就是第 ii 行第 jj 列的格子上所填入的数应为 T(i−1)M+jT_{(i-1)M+j}​​ 。

接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 NN 行第 MM 列的格子。

小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 N+M−1N+M-1 的升序序列，我们称之为路径序列。

小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？

Constraints

2≤N,M≤50002 \leq N,M \leq 5000

Solution

按照题意模拟一遍将数组求出来，然后从小到大填依次判断是否可行即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=5005;
const int M=25000005;
int n,m,q,s,X,Y,cnt;
LL a,b,c,d;
int x[M],t[M],l[N],r[N],ans[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	x[0]=read();a=read();b=read();c=read();d=read();
	n=read();m=read();q=read();s=n*m;
	for(int i=1;i<=s;i++)
		x[i]=(x[i-1]*(x[i-1]*a+b)+c)%d,t[i]=i;
	for(int i=1;i<=s;i++)
		swap(t[i],t[(x[i]%i)+1]);
	for(int i=1;i<=q;i++)
		X=read(),Y=read(),swap(t[X],t[Y]);
	for(int i=1;i<=s;i++)x[t[i]]=i;
	memset(r,0x3f,sizeof(r));
	for(int i=1;i<=s;i++)
	{
		X=(x[i]-1)/m+1;
		Y=x[i]%m;if(!Y)Y+=m;
		if(Y>=l[X]&&Y<=r[X])
		{
			for(int j=1;j<=n;j++)
			{
				if(j<X)r[j]=min(r[j],Y);
				if(j>X)l[j]=max(l[j],Y);
			}
			ans[++cnt]=i;
			if(cnt==n+m-1)break;
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		printf("%d",ans[i]);
		if(i!=cnt)putchar(' ');
	}
	return 0;
}