随机数生成器

生成棋盘排列后,按数值从小到大尝试选格;维护每行可选列区间,得到排序后字典序最小的右上/右下路径序列。

来源 Luogu P2354 · 标签 贪心 / 构造 / 模拟 / 区间

题目描述

给定随机种子 𝑥0,𝑎,𝑏,𝑐,𝑑,先按

𝑥𝑖=(𝑎𝑥𝑖−12+𝑏𝑥𝑖−1+𝑐)mod𝑑

生成随机序列。令 𝐾=𝑁𝑀,初始排列 𝑇𝑖=𝑖。对 𝑖=1,…,𝐾,交换 𝑇𝑖 与 𝑇(𝑥𝑖mod𝑖)+1;再进行 𝑄 次额外交换。

把最终的 𝑇 逐行填入 𝑁 行 𝑀 列的棋盘。从 (1,1) 出发,每次向右或向下走到 (𝑁,𝑀)。把路径上的 𝑁+𝑀−1 个数排序,得到路径序列。

求字典序最小的路径序列。

2≤𝑁,𝑀≤5000,𝑁𝑀≤2.5×107。

题解

先生成排列 𝑇 和棋盘,并记录每个数所在的格子。

答案序列已经排序,因此按数值 1,2,…,𝐾 依次尝试:若当前数所在的格子还能出现在某条合法路径上,就选它;否则跳过。这样每一步都取当前能取的最小值,得到的就是字典序最小的序列。

为了判断“还能出现在路径上”,维护每一行当前允许的列区间 [𝐿𝑟,𝑅𝑟],初始为 [1,𝑀]。设当前数为 𝑣,位置为 (𝑟,𝑐):

  • 若 𝑐∉[𝐿𝑟,𝑅𝑟],跳过;
  • 否则选中 𝑣,并更新:

    • 对所有 𝑖<𝑟,令 𝑅𝑖←min(𝑅𝑖,𝑐);
    • 对所有 𝑖>𝑟,令 𝐿𝑖←max(𝐿𝑖,𝑐)。

原因是路径经过 (𝑟,𝑐) 后,它上方的行不能走到 𝑐 的右侧,下方的行不能走到 𝑐 的左侧。区间被不断收缩,后续数是否可选只需查它所在行的区间。

选到 𝑁+𝑀−1 个数后停止,按选中的顺序输出。

复杂度

生成排列和棋盘为 𝑂(𝑁𝑀+𝑄)。贪心最多选 𝑁+𝑀−1 个数,每次更新 𝑂(𝑁) 行,总时间为 𝑂(𝑁(𝑁+𝑀)),空间为 𝑂(𝑁𝑀)。

参考

源码位置