AC. 梦想

frank_c1

[NOI 2014] 随机数生成器

发布于2016年01月19日 | 暂无评论 | 732阅读 | 模拟,贪心

题目描述

小H最近在研究随机算法。随机算法往往需要通过调用随机数生成函数(例如Pascal中的random和C/C++中的rand)来获得随机性。事实上,随机数生成函数也并不是真正的“随机”,其一般都是利用某个算法计算得来的。

比如,下面这个二次多项式递推算法就是一个常用算法:

算法选定非负整数x_0,a,b,c,d作为随机种子,并采用如下递推公式进行计算。

对于任意i\ge 1,x_i= \left(ax_{i-1}^2+bx_{i-1}+c \right) \bmod d

这样可以得到一个任意长度的非负整数数列\{x_i\}_{i\ge 1},一般来说,我们认为这个数列是随机的。

利用随机序列\{x_i\}_{i\ge 1},我们还可以采用如下算法来产生一个1K随机排列\{T_i\}_{i=1}^K

1. 初始设T1K的递增序列;

2. 对T进行K次交换,第i次交换,交换T_iT_{(x_i \bmod i)+1} 的值。

此外,小H在这K次交换的基础上,又额外进行了Q次交换操作,对于第i次额外交换,小H会选定两个下标u_iv_i,并交换T_{u_i}T_{v_i}的值。

为了检验这个随机排列生成算法的实用性,小H设计了如下问题:

小H有一个NM列的棋盘,她首先按照上述过程,通过N \times M+Q次交换操作,生成了一个 1 \sim N \times M的随机排列\{T_i\}_{i=1}^{N\times M}然后将这N\times M个数逐行逐列依次填入这个棋盘:也就是第 i 行第 j 列的格子上所填入的数应为T_{(i-1)\times M+j}

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

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

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

输入格式

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

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

接下来Q行,第i行包含两个整数u_i,v_i,表示第i次额外交换操作将交换 T_{u_i}T_{v_i}的值。

输出格式

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

题目解析

这题的题目描述真长…… 然而并不是很难。

首先,按题目要求生成一个棋盘。由于题目要取字典序最小的路径序列,所以我们处理出 1 - NM在棋盘中的位置,依次判断,如果可以和当前答案组成一条合法的路径,那么加入答案并更新,直到取满 N+M-1 个。具体可以维护行i当前允许的左端点left[i]和右端点right[i],判断是否可存在于路径中O(1),更新信息O(N)

此题另一个需要注意的地方是空间。由于数据规模比较大,NM的数组只能开两个,需要循环利用。