格点染色 - 题解

标签与难度

标签: 组合计数, 乘法原理, 思维题, 构造难度: 1700

题目大意喵~

主人你好呀~！这道题是这样的：我们有一排 $n$ 个格子，从 1 到 $n$ 编号，一开始都是没有颜色的。我们的小爪子一开始在第 1 格。

当我们在第 $x$ 格的时候，可以做两件事，选一个就好：

散步：直接走到第 $x+1$ 格去。
染色跳跃：如果第 $x$ 格还没被染色，我们可以把它染成黑色，然后“咻”的一下跳到第 $a_x$ 格。

我们的目标是把所有 $n$ 个格子都染成黑色。题目问的是，有多少种不同的染色顺序可以达成这个目标呢？比如说，先染 1 号再染 3 号再染 2 号，和先染 3 号再染 1 号再染 2 号，是不同的顺序哦。最后答案要对 $10^9 + 7$ 取模，喵~

解题思路分析

喵呜~ 这道题看起来像是一个复杂的路径规划或者动态规划问题，如果直接从头开始模拟所有可能的选择，状态会爆炸的！(⊙o⊙) 我们会发现自己在哪，哪些格子被染了色，这些信息都得记下来，太复杂啦。

所以，我们要换个角度思考，从问题的结构本身入手，呐。这种要求计算“方案数”并且答案形式很简洁的题目，通常背后都有巧妙的组合计数原理！

让我们不从前往后（从 1 到 $n$ ）思考，而是从后往前（从 $n$ 到 1）来分析问题的结构。

核心思想：解耦依赖关系

我们可以把整个染色过程看作是对 $n$ 个染色任务 $\{C_1, C_2, \dots, C_n\}$ 进行排序，其中 $C_i$ 代表“把第 $i$ 格染黑”这个事件。我们的目标就是计算有多少个合法的排列。

一个排列是合法的，当且仅当我们可以构造一个操作序列（散步、染色跳跃）来依次完成这个排列中的染色任务。

从最大的格子 n 开始分析

考虑与第 $n$ 格相关的这组格子： $S_n = \{a_n, a_n+1, \dots, n\}$ 。想一想，当我们进行操作时，一旦我们对第 $n$ 格进行了染色，我们就会立即跳到 $a_n$ 格。这意味着，在 $C_n$ 这个事件发生之后，我们后续的探索都将从 $a_n$ 这个位置开始（或者其他因为别的染色跳跃而产生的起点）。因为 $a_n \le n$ ，我们不可能通过 $n \to n+1$ 的方式再回头染上 $n$ 左边的格子。

这启发我们，关于 $S_n$ 中这些格子的染色顺序，可以看作一个独立的子问题。它们之间的染色顺序，与 $S_n$ 之外的格子关系不大，只在于我们什么时候进入这个“代码块”以及从哪个“出口”（即 $a_k$ for $k \in S_n$ ）跳出。

最关键的洞察来了：在 $S_n = \{a_n, a_n+1, \dots, n\}$ 这个集合中，任何一个格子都可以是最后一个被染色的。

为什么呢？假设我们决定让 $k \in S_n$ 成为 $S_n$ 中最后一个被染色的格子。

我们可以先完成所有 $S_n \setminus \{k\}$ 中格子的染色任务。每次染色，我们都会跳到某个 $a_j \le a_n \le k$ 的位置。
无论我们跳到哪里，我们总能通过一系列“散步”操作（ $x \to x+1$ ）再次到达未染色的格子。因为所有 $S_n \setminus \{k\}$ 都被染了，我们可以自由地在这些格子上移动。
最终，我们可以找到一条路径到达 $k$ ，把它染上色。

因此，对于 $S_n$ 这个集合，我们有 $|S_n| = n - a_n + 1$ 种选择，来决定哪一个格子是这个集合里最后一个被染色的。

递推关系

当我们在 $S_n$ 中选定了最后一个被染色的格子 $k$ 后，整个 $S_n$ 的染色任务可以被看作一个“黑盒”。完成这个黑盒后，我们会从 $a_k$ 这个位置跳出。现在，问题规模缩小了，我们只需要考虑剩下的格子。

我们可以把这个逻辑推广。从 $i = n$ 到 $1$ 进行考虑：

当考虑第 $i$ 格时，我们分析集合 $S_i = \{a_i, a_i+1, \dots, i\}$ 。
在任何合法的染色顺序中，这 $i-a_i+1$ 个格子之间存在着紧密的联系。我们可以独立地考虑它们的相对染色顺序。
与上面的论证类似，在 $S_i$ 这个集合中，任何一个格子都可以是它们之间最后一个被染色的。这为我们提供了 $i - a_i + 1$ 个选择。

根据乘法原理，总的染色顺序数就是把每一步的选择数相乘。

对于 $i=n$ ，我们有 $n - a_n + 1$ 种选择（决定 $S_n$ 中谁最后被染）。
对于 $i=n-1$ ，我们有 $(n-1) - a_{n-1} + 1$ 种选择。
...
对于 $i=1$ ，我们有 $1 - a_1 + 1$ 种选择。

所以，总方案数就是：

\text{Total Ways} = \prod_{i=1}^{n} (i - a_i + 1)

这个过程我们是从 $n$ 倒推回 1，但在计算时，从 1 循环到 $n$ 来累乘是完全一样的，喵~

举个栗子： $n=3, a=\{1, 1, 2\}$

$i=1$ : 贡献是 $1 - a_1 + 1 = 1 - 1 + 1 = 1$
$i=2$ : 贡献是 $2 - a_2 + 1 = 2 - 1 + 1 = 2$
$i=3$ : 贡献是 $3 - a_3 + 1 = 3 - 2 + 1 = 2$ 总方案数 = $1 \times 2 \times 2 = 4$ 种。

这个思路是不是比直接模拟清晰多啦？喵~

代码实现

这只我这就把思路变成代码，主人请看~

cpp

#include <iostream>

// 为了让代码更清晰，我们定义一些常量和类型别名
using ll = long long;
const int MOD = 1e9 + 7;

int main() {
    // 使用C++标准IO，并关闭同步，让输入输出更快一些，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // 格子的总数
    std::cin >> n;

    ll total_ways = 1; // 用来累计总方案数，初始化为1

    // 我们从 1 到 n 遍历每个格子
    for (int i = 1; i <= n; ++i) {
        int jump_target; // 当前格子 i 的跳跃目标 a_i
        std::cin >> jump_target;

        // 根据我们的推导，在处理第 i 个格子时，
        // 有 (i - a_i + 1) 种独立的方案选择。
        // 我们将这个选择数乘到总方案数中。
        ll current_choices = i - jump_target + 1;
        
        // 每次相乘后都要取模，防止结果溢出 long long 的范围
        total_ways = (total_ways * current_choices) % MOD;
    }

    // 所有格子的选择都乘起来之后，就是最终的答案啦
    std::cout << total_ways << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们只需要一个循环，从 1 遍历到 $n$ ，读取每个 $a_i$ 并进行一次乘法和取模操作。所以时间复杂度和格子的数量 $N$ 是线性关系，非常高效！
空间复杂度: $O(1)$ 我们不需要存储所有的 $a_i$ 值。在循环中，我们读一个用一个，只需要几个变量来保存当前的状态（如 n, total_ways, jump_target）。所以，除了输入本身，我们几乎没有使用额外的空间，喵~

知识点总结

这道题虽然伪装成一个复杂的操作模拟题，但它的核心是一个漂亮的组合计数问题。

转换视角: 解决复杂计数问题的关键技巧之一，就是从不同的角度看待问题。从正向模拟（操作序列）切换到反向构造（分析依赖关系），往往能让问题豁然开朗。
乘法原理: 当一个过程可以分解为多个独立的步骤，且每一步的选择数不受其他步骤的具体选择影响时，总方案数就是每一步方案数的乘积。这里，我们把对 $n$ 个格子的染色问题，分解成了 $n$ 个独立的关于“谁在某个子集中最后被染”的决策。
解耦: 识别和分离问题中的依赖关系是解题的核心。我们通过从 $i=n$ 开始分析，成功地将复杂的全局依赖关系分解成了局部块内的决策。

希望我的题解能帮助到你！如果还有不明白的地方，随时可以再来问哦，喵~ >w<

格点染色 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​