CF207A2 Beaver's Calculator 1.0

ABBYY 的聪明海狸再次让我们大吃一惊！他开发了一种新的计算设备，称之为“海狸计算器 $1.0$”。这种设备非常特别，计划用于各种科学问题。 为了测试它，聪明海狸邀请了 $n$ 位科学家，编号从 $1$ 到 $n$。第 $i$ 位科学家为聪明海狸开发的设备带来了 $k_i$ 个计算问题。第 $i$ 位科学家的问题编号从 $1$ 到 $k_i$，这些问题必须按照给定顺序依次计算，因为每个问题的计算都严重依赖于前一个问题的结果。 每位科学家的每个问题由一个整数 $a_{i,j}$ 描述，其中 $i$（$1 \leq i \leq n$）是科学家的编号，$j$（$1 \leq j \leq k_i$）是问题的编号，$a_{i,j}$ 是计算设备解决该问题所需的资源单元数。 聪明海狸开发的计算设备非常特殊。它会依次逐个解决问题。在解决完一个问题后、开始下一个问题之前，计算设备会分配或释放资源。 对于计算设备来说，释放资源是最昂贵的操作，比分配资源慢得多。因此，希望每个下一个问题所需的资源不少于前一个问题。 你得到了科学家们为测试提供的问题的信息。你需要安排这些问题的顺序，使得在这个列表中相邻的“坏”问题对的数量尽可能少。我们称列表中连续的两个问题为“坏对”，如果先解决的问题所需资源比后一个多。不要忘记，同一位科学家的问题必须按照固定顺序解决。

第一行包含一个整数 $n$，表示科学家的数量。为了减小输入规模，接下来的 $n$ 行每行包含五个整数 $k_i$、$a_{i,1}$、$x_i$、$y_i$、$m_i$（$0 \leq a_{i,1} < m_i \leq 10^9$，$1 \leq x_i, y_i \leq 10^9$），分别表示第 $i$ 位科学家的问题数量、首个问题所需资源以及生成后续 $a_{i,j}$ 的三个参数。对于所有 $j$ 从 $2$ 到 $k_i$，你需要用如下公式计算 $a_{i,j}$： $$ a_{i,j} = (a_{i,j-1} \times x_i + y_i) \bmod m_i $$ 其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。 对于第一组测试，$n=2$，$1 \leq k_i \leq 2000$ 即可获得满分。 对于第二组测试，$n=2$，$1 \leq k_i \leq 200000$ 即可获得满分。 对于第三组测试，$1 \leq n \leq 5000$，$1 \leq k_i \leq 5000$ 即可获得满分。

第一行输出一个整数，表示最优顺序下“坏对”的数量。 如果所有问题的总数不超过 $200000$，还需输出如下行数，每行两个整数，分别表示该问题所需的资源数和提出该问题的科学家编号，之间用一个空格隔开。科学家编号按输入顺序从 $1$ 到 $n$。

在第一个样例中，$n=2$，$k_1=2$，$a_{1,1}=1$，$a_{1,2}=2$，$k_2=2$，$a_{2,1}=3$，$a_{2,2}=4$。我们有两位科学家，每人有两个计算问题。第一位科学家的问题分别需要 $1$ 和 $2$ 单位资源，第二位科学家的问题分别需要 $3$ 和 $4$ 单位资源。我们列出所有可能的计算顺序（每个问题仅用其所需资源数表示）：$(1,2,3,4)$，$(1,3,2,4)$，$(3,1,2,4)$，$(1,3,4,2)$，$(3,4,1,2)$，$(3,1,4,2)$。 问题序列 $(1,3,2,4)$ 有一个“坏对”（$3$ 和 $2$），$(3,1,4,2)$ 有两个“坏对”（$3$ 和 $1$，$4$ 和 $2$），而 $(1,2,3,4)$ 没有“坏对”。 由 ChatGPT 4.1 翻译