题目地址：洛谷：【P2354】[NOI2014]随机数生成器 – 洛谷、BZOJ：Problem 3671. — [Noi2014]随机数生成器

题目描述

小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C++中的 rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。
比如，下面这个二次多项式递推算法就是一个常用算法：
算法选定非负整数 x0,a,b,c,d 作为随机种子，并采用如下递推公式进行计算。
对于任意 i ≥ 1, xi=(a*x[i-1]^2+b*x[i-1]+c)mod d 这样可以得到一个任意长度的非负整数数列{xi},i≥1，一般来说，我们认为这个数列是随机的。
利用随机序列{xi},i≥1，我们还可以采用如下算法来产生一个 1 到 K 的随机排列{Ti},i=1 to k：

1. 初始设 T 为 1 到 K 的递增序列；
2. 对 T 进行 K 次交换，第 i 次交换，交换 Ti 和 T[xi mod i + 1] 的值。

此外，小 H 在这 K 次交换的基础上，又额外进行了 Q 次交换操作，对于第i 次额外交换，小 H 会选定两个下标 ui 和 vi，并交换 T[ui] 和 T[vi] 的值。
为了检验这个随机排列生成算法的实用性，小 H 设计了如下问题：
小 H 有一个 N 行 M 列的棋盘，她首先按照上述过程，通过 N × M + Q 次交换操作，生成了一个 1~N × M 的随机排列 {Ti},i=1 to N*M，然后将这 N × M 个数逐行逐列依次填入这个棋盘：也就是第 i 行第 i 列的格子上所填入的数应为 T[(i-1)*M+uj]。
接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 N 行第M 列的格子。
小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 N + M − 1 的升序序列，我们称之为路径序列。
小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？

题意简述

我们有一个随机序列生成算法，对于给定的$x_0, a, b, c, d$，有$x_i = (ax_{i-1}^2 + bx_{i-1} + c) \bmod d$。我们可以利用序列$x_i$来生成随机排列$T_i$，对于一个长为$k$的顺序排列$T_i$，我们进行$k$次交换，每次交换$T_i$和$T_{x_i \bmod i + 1}$。
我们有一个$n \times m$的矩阵，现在，我们按照上面的方法生成一个$n \times m$的随机排列，另外，给出$q$次额外交换，每次交换排列中$T_{u_i}$和$T_{v_i}$两个位置。然后，把这个排列放进矩阵中，即，矩阵$A$的元素$A_{i, j}$上填入$T_{(i-1)m+j}$。
现在，我们需要找到一条从矩阵左上角$(1, 1)$出发，每次向右或向下走一格，到右下角$(n, m)$的路径，这条路径上经过的格子的数字构成了一个长度$n+m-1$的序列，现在想求排序后字典序最小的这样的序列。

输入输出格式

输入格式：
第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 ) 的值。

输出格式：
输出一行，包含 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 个随机数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-28。

题解

略有些无聊的卡空间阅读题。
首先，我们按照题目的要求处理出$T_i$，然后，发现开三个$5000 \times 5000$的int数组显然会爆炸，于是我们考虑重复利用最开始的$x_i$数组来存储每个数在$T_i$中的下标。
显然我们可以从小到大贪心地选择每个可行的数字，选择一个数字会对它所在行之前行可选择的列的右端点左移至该数所在列，且之后行可选择的列的左端点右移至该数所在列，我们开两个$5000$大小的int数组来存每一行能选择的列区间即可。
复杂度$O(nm)$，卡常卡空间，尽量控制吧。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline int min(int a, int b) {
    return a < b ? a : b;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 5005;

LL a, b, c, d;
int n, m, q, x[MAXN * MAXN], T[MAXN * MAXN], l[MAXN], r[MAXN];

int main() {
    x[0] = readint(); a = readint(); b = readint(); c = readint(); d = readint();
    n = readint(); m = readint(); q = readint();
    for(int i = 1; i <= n * m; i++) {
        x[i] = (1ll * a * x[i - 1] * x[i - 1] + 1ll * b * x[i - 1] + c) % d;
    }
    for(int i = 1; i <= n * m; i++) {
        T[i] = i;
    }
    for(int i = 1; i <= n * m; i++) {
        std::swap(T[i], T[x[i] % i + 1]);
    }
    while(q--) {
        int u = readint(); int v = readint();
        std::swap(T[u], T[v]);
    }
    for(int i = 1; i <= n * m; i++) {
        x[T[i]] = i;
    }
    for(int i = 1; i <= n; i++) {
        r[i] = m + 1;
    }
    int cnt = 0;
    for(int i = 1; i <= n * m; i++) {
        int X = x[i] / m + 1, Y = x[i] % m;
        if(!Y) { X--; Y += m; }
        if(Y >= l[X] && Y <= r[X]) {
            printf("%d ", i); cnt++;
            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);
            }
        }
        if(cnt >= n * m - 1) break;
    }
    return 0;
}