CF207A1 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-1} \times x_i + y_i) \bmod m_i$ 计算 $a_{i,j}$，其中 $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 翻译