CF1696E Placing Jinas

我们称一个无限序列 $a_0, a_1, a_2, \ldots$ 是非递增的，当且仅当对于所有 $i \ge 0$，都有 $a_i \ge a_{i+1}$。 有一个无限大的向右和向下延伸的网格。左上角的格子的坐标为 $(0,0)$。行从上到下编号为 $0$ 到无穷大，列从左到右编号为 $0$ 到无穷大。 同时给定一个非递增的无限序列 $a_0, a_1, a_2, \ldots$。你已知 $a_0, a_1, \ldots, a_n$；对于所有 $i > n$，有 $a_i = 0$。对于每一对 $x, y$，坐标为 $(x, y)$ 的格子（即第 $x$ 行第 $y$ 列的格子）是白色的当且仅当 $y < a_x$，否则为黑色。 初始时，$(0,0)$ 上有一个名为 Jina 的娃娃。你可以进行如下操作： - 选择一个在 $(x, y)$ 的娃娃，将其移除，并在 $(x, y+1)$ 和 $(x+1, y)$ 各放置一个娃娃。 注意，一个格子上可以同时有多个娃娃；每次操作只移除一个娃娃。你的目标是让所有白色格子上的娃娃数变为 $0$。 请问最少需要多少次操作才能达成目标？请输出答案对 $10^9+7$ 取模。

输入的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。 第二行包含 $n+1$ 个整数 $a_0, a_1, \ldots, a_n$（$0 \le a_i \le 2 \times 10^5$）。 保证序列 $a$ 是非递增的。

输出一个整数，表示问题的答案，对 $10^9+7$ 取模。

以第一个样例为例。在给定的网格中，$(0,0),(0,1),(1,0),(1,1)$ 是白色格子，其他格子都是黑色。我们用三元组 $(x, y, z)$ 表示网格状态，表示在 $(x, y)$ 上有 $z$ 个娃娃。初始时网格状态为 $(0,0,1)$。 一种最优的操作序列如下： - 对 $(0,0)$ 进行操作。此时网格状态为 $(1,0,1),(0,1,1)$。 - 对 $(0,1)$ 进行操作。此时网格状态为 $(1,0,1),(1,1,1),(0,2,1)$。 - 对 $(1,0)$ 进行操作。此时网格状态为 $(1,1,2),(0,2,1),(2,0,1)$。 - 对 $(1,1)$ 进行操作。此时网格状态为 $(1,1,1),(0,2,1),(2,0,1),(1,2,1),(2,1,1)$。 - 再对 $(1,1)$ 进行操作。此时网格状态为 $(0,2,1),(2,0,1),(1,2,2),(2,1,2)$。 此时所有白色格子上的娃娃数都为 $0$，因此我们用 $5$ 次操作达成了目标。 由 ChatGPT 4.1 翻译