Ryan_<

题意：

利用二次多项式递推算法得到一个非负整数随机数列

通过对递增排列进行交换得到一个1~K随机排列

将得到的排列填入N*M的棋盘内，从左上角走到右下角，经过路径上的数字从小到大排序，求可以得到的字典序最小的路径序列。

N,M<=5000，交换次数Q<=50000，时限5s，内存限制256MB

分析：

排列生成直接暴力！我还以为是像SDOI那道随机数生成器一样是数论题呢。

不需要开二维数组，直接对序列进行处理即可。但空间是卡着过去的，可以开short int。

预处理出1~n的位置：二进制存储！二进制前16位储存行，后16位储存列（2^16足够），提取时直接位运算分别得到行列数即可（pv=posvalue，该值的位置）

	F(i,1,n) F(j,1,m) pv[mp[i][j]]=i<<16|j;
	F(i,1,m*n){
		int x=pv[i]>>16;
		int y=pv[i]&65535;
        }

从小到大枚举数字1~n*m，贪心填入（每次都将填入当前位置允许的最小数字）。由于行走方向只可以向右或向下，将当前填入的数字的左下角和右上角标记为无法填入数字，具体实现 将每行合法区间的左右端点修改即可，填数的复杂度是O（n^2）的！

一般区间覆盖的题目会想到线段树，但这道题线段树维护暴力修改操作是O（n^2logn）的。靠大脑吧少年！

代码学习了POPOQQQ大爷的~

int seed,A,B,C,D;
const int N=5000+10;
int n,m,q,T[N*N],l[N],r[N];
int mp[N][N],pv[N*N];
bool flag;
int Rand(){return seed=(A*seed*seed+B*seed+C)%D;}//return时仍赋值
void kill(int x,int y)
{
	F(i,1,x-1) r[i]=min(r[i],y);
	F(i,x+1,n) l[i]=max(l[i],y);
}
Ryan main()
{
	#ifndef ONLINE_JUDGE
//	freopen("random.in","r",stdin); 
	#endif
	scanf("%d%d%d%d%d",&seed,&A,&B,&C,&D);
	scanf("%d%d%d",&n,&m,&q);flag=0;
	F(i,1,n) l[i]=1,r[i]=m;
	F(i,1,m*n) T[i]=i,swap(T[i],T[Rand()%i+1]);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		swap(T[x],T[y]); 
	}
	int k=0;
	F(i,1,n) F(j,1,m) mp[i][j]=T[++k];
	F(i,1,n) F(j,1,m) pv[mp[i][j]]=i<<16|j;
	F(i,1,m*n){
		int x=pv[i]>>16;
		int y=pv[i]&65535;
		if(l[x]<=y&&y<=r[x]){
			if(flag) putchar(' ');
			flag=1;
			printf("%d",i);
			kill(x,y);		
		}
	}
	return 0;	
}

UPD:等等，似乎get到了一种生成随机排列的方法！？

int Rand()
{
	return seed=(A*seed*seed+B*seed+C)%D;
}//return时赋值

for(int i=1;i<=n;i++)
	P[i]=i,swap(P[i],P[Rand()%i+1]);