Birthday Reminders - 题解

标签与难度

标签: 动态规划, 计数DP, 前缀和优化DP, 组合数学难度: 2200

题目大意喵~

nya好！各位算法大师们，今天我们要帮助 Tomori 小姐解决一个生日祝福的难题！事情是这样哒：

Tomori 有 $N$ 个朋友。

有些朋友会自己记得 Tomori 的生日，并在特定的时间 $t_i$ 送上祝福。如果 $t_i = -1$ ，就说明这位朋友自己想不起来。
朋友之间还有个“提醒链”！如果朋友 $i$ 在时间 $t$ 送上了祝福，他/她会立刻提醒朋友 $p_i$ 。那么朋友 $p_i$ 就会在时间 $t+1$ 送上祝福（当然，前提是 $p_i$ 之前还没送过祝福哦）。
这个提醒关系 $\{p_1, p_2, \dots, p_N\}$ 是一个排列，也就是说，每个朋友都只会被唯一一个其他朋友提醒。
一个人最终送出祝福的时间，是他/她自己记起的时间和所有被提醒的时间中，最早的那一个。

Tomori 因为太开心了，分不清是谁在什么时候送的祝福，她只知道在每个时间点收到了多少份祝福。比如，她知道“时间0收到了2份，时间1收到了3份，时间2收到了1份……”。

我们的任务是，计算在所有可能的提醒排列 $p$ 下，Tomori 可能经历多少种不同的“生日体验”？两种体验只要在任何一个时间点收到的祝福数量不同，就算作不同。结果需要对 $10^9 + 7$ 取模，喵~

解题思路分析

这道题看起来和排列有关，但直接去枚举 $N!$ 种排列肯定是行不通的，太可怕了喵！(>ω<) 关键在于题目问的是不同的“生日体验”，也就是不同的时间点祝福数量序列。Tomori 分不清朋友，所以我们也不用关心具体是谁在祝福，只需要关心数量！这给了我们一个重要的提示：问题可以从“排列”转化为“计数”。

让我们来分析一下，一个祝福数量序列 (c_0, c_1, c_2, ...)（其中 $c_t$ 是时间 $t$ 的祝福数）要成为可能，需要满足什么条件呢？

假设 cnt[t] 是初始就在时间 $t$ 记得送祝福的朋友数量。

累积祝福约束：到时间 $t$ 为止，所有应该自己记起生日的朋友（即 $t_i \le t$ 的朋友）都必须已经送出祝福了。因为他们最晚也会在自己记得的时间送出，可能会被提醒得更早，但绝不会更晚。所以，在时间 $t$ 结束时，总祝福数必须至少等于此刻及之前所有初始祝福的总和。
$\sum_{k=0}^{t} c_k \ge \sum_{k=0}^{t} \text{cnt}[k]$
祝福来源约束：在时间 $t+1$ 送出祝福的 $c_{t+1}$ 位朋友，他们为什么会在这时送祝福呢？只有两种可能：
- 他们是初始就在时间 $t+1$ 记得的（有 cnt[t+1] 人）。
- 他们是被在时间 $t$ 送祝福的 $c_t$ 位朋友中的某一位提醒的。这 $c_t$ 位朋友可以提供 $c_t$ 个“提醒名额”。所以，在时间 $t+1$ ，总共有 $c_t + \text{cnt}[t+1]$ 个“祝福的理由”。真正送出祝福的人数 $c_{t+1}$ 当然不能超过这个数啦。
$c_{t+1} \le c_t + \text{cnt}[t+1]$

只要一个祝福数序列满足上述两个条件，我们总能构造出一个对应的排列 $p$ 。所以问题就转化成了：计算有多少个满足这两个条件的序列 (c_0, c_1, ...)。

这是一个典型的计数问题，非常适合用动态规划（DP）来解决，喵！

DP状态设计

我们需要记录序列的演变过程。DP的状态需要包含哪些信息呢？

当前进行到哪个时间点了。
到目前为止，总共有多少人送了祝福。
在上一个时间点，有多少人送了祝福（因为这会影响当前时间点的祝福数上限）。

于是，我们可以定义一个三维DP状态： dp[i][j][k] 表示：考虑完时间点 0到 i-1，总共有 j 位朋友送了祝福，其中在时间点 i-1 有 k 位朋友送祝福的方案数。

DP转移方程

我们采用“拉动”（pull）的方式来构建DP。也就是说，我们计算 dp[i][j][k] 的值，是通过从 dp[i-1] 的各个状态“拉取”贡献。

要计算 dp[i][j][k]，我们思考一下：

当前是时间点 i-1，祝福人数为 k。
总祝福人数为 j。
那么在时间点 i-2 结束时，总祝福人数就是 j-k。
设在时间点 i-2 有 l 人送祝福。

这个状态 (i, j, k) 可以从前一个状态 (i-1, j-k, l) 转移而来。我们需要对所有合法的 l 进行求和。

dp[i][j][k] = \sum_{l} dp[i-1][j-k][l]

那么，l 的取值范围是什么呢？根据我们的“祝福来源约束”，在时间 i-1 的祝福数 k，不能超过在时间 i-2 的祝福数 l 加上在时间 i-1 初始记得的人数 cnt[i-1]。 $k \le l + \text{cnt}[i-1] \implies l \ge k - \text{cnt}[i-1]$ 。同时，l 作为在 i-2 时间点的祝福数，不能超过当时的总祝福数 j-k。所以 l 的范围是 max(0, k - cnt[i-1]) <= l <= j-k。

朴素的转移方程是：

dp[i][j][k] = \sum_{l=\max(0, k - \text{cnt}[i-1])}^{j-k} dp[i-1][j-k][l]

同时，状态 (i, j, k) 本身也必须满足“累积祝福约束”，即 $j \ge \sum_{t=0}^{i-1} \text{cnt}[t]$ 。

复杂度与优化

这个DP的时间复杂度是 $O(\text{时间} \times N \times N \times N)$ ，因为有三层状态循环，转移还需要一层循环。对于 $N=200$ 来说，这太慢啦，会超时的说！

但是，我们注意到转移方程中的求和是对 l 在一个连续区间上的求和！这是一个经典信号，可以用前缀和来优化，喵~

我们定义一个前缀和数组 prefix_sum_dp[i][total][max_l]：

\text{prefix\_sum\_dp}[i][\text{total}][\text{max\_l}] = \sum_{l'=0}^{\text{max\_l}} dp[i][\text{total}][l']

这样，上面那个求和就可以 $O(1)$ 计算了：

\sum_{l=L}^{R} dp[i-1][j-k][l] = \text{prefix\_sum\_dp}[i-1][j-k][R] - \text{prefix\_sum\_dp}[i-1][j-k][L-1]

优化后，转移就变成了 $O(1)$ ，总时间复杂度降为 $O(\text{时间} \times N \times N)$ ，大概是 $O(N^3)$ 。考虑到最大时间不会超过 $N$ （因为每次至少有一个人祝福才能延续链条），这个复杂度就非常稳妥了！

最终答案

我们把DP算到足够大的时间（比如 $N+1$ ），最终的答案就是所有可能的最终状态的总和。

\text{Ans} = \sum_{j=0}^{N} \sum_{k=0}^{N} dp[\text{max\_time}][j][k]

好啦，思路清晰了，让我们动手实现吧！

代码实现

cpp

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;

// 辅助函数，用于模块化加法
void add(int &a, int b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

int main() {
    // 使用C++标准IO，并关闭同步以加速，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // max_time 设为 n+2 足够了，因为祝福链最长也就是 n
    int max_time = n + 2; 
    vector<int> initial_wish_counts(max_time, 0);
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        if (t != -1) {
            initial_wish_counts[t]++;
        }
    }

    // 计算初始祝福的累积和，用于检查DP状态的合法性
    vector<int> cumulative_initial_wishes(max_time, 0);
    cumulative_initial_wishes[0] = initial_wish_counts[0];
    for (int i = 1; i < max_time; ++i) {
        cumulative_initial_wishes[i] = cumulative_initial_wishes[i - 1] + initial_wish_counts[i];
    }

    // dp[i][j][k]: 考虑完时间 0 到 i-1, 共 j 人祝福, 其中 i-1 时刻有 k 人祝福的方案数
    vector<vector<vector<int>>> dp(max_time + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
    
    // prefix_sum_dp[i][j][k]: sum of dp[i][j][l] for l from 0 to k
    vector<vector<vector<int>>> prefix_sum_dp(max_time + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));

    // Base Case: 在时间 -1 (即开始前), 0 人祝福, 0 人在 -1 时刻祝福, 这是一种虚拟的初始状态
    dp[0][0][0] = 1;
    for (int k = 0; k <= n; ++k) {
        prefix_sum_dp[0][0][k] = 1;
    }

    // 开始DP！时间 i 从 1 到 max_time
    for (int i = 1; i <= max_time; ++i) {
        // j 是到时间 i-1 为止的总祝福数
        for (int j = 0; j <= n; ++j) {
            // 累积祝福约束检查
            if (j < cumulative_initial_wishes[i - 1]) {
                continue;
            }
            
            // k 是在时间 i-1 的祝福数
            for (int k = 0; k <= j; ++k) {
                // l 的下界，由祝福来源约束决定
                int l_min = max(0, k - initial_wish_counts[i - 1]);
                // l 的上界，不能超过当时的总祝福数 j-k
                int l_max = j - k;

                if (l_min > l_max) {
                    continue;
                }
                
                // 使用前缀和 O(1) 计算转移
                int sum_val = prefix_sum_dp[i - 1][j - k][l_max];
                if (l_min > 0) {
                    add(sum_val, MOD - prefix_sum_dp[i - 1][j - k][l_min - 1]);
                }
                dp[i][j][k] = sum_val;
            }

            // 计算当前时间 i 的前缀和，为下一轮DP做准备
            prefix_sum_dp[i][j][0] = dp[i][j][0];
            for (int k = 1; k <= n; ++k) {
                prefix_sum_dp[i][j][k] = prefix_sum_dp[i][j][k-1];
                add(prefix_sum_dp[i][j][k], dp[i][j][k]);
            }
        }
    }

    // 最终答案是所有在 max_time 结束时的状态总和
    int total_possible_days = 0;
    for (int j = 0; j <= n; ++j) {
        for (int k = 0; k <= j; ++k) {
            add(total_possible_days, dp[max_time][j][k]);
        }
    }

    cout << total_possible_days << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot N^2)$ , 其中 $T$ 是我们模拟的最大时间（取 $N+2$ 足够）， $N$ 是朋友的数量。我们有三个嵌套循环：时间 i ( $0$ to $T$ ), 总祝福数 j ( $0$ to $N$ ), 和当前时间祝福数 k ( $0$ to $N$ )。由于使用了前缀和优化，每次状态转移的计算是 $O(1)$ 的。所以总复杂度是 $O(T \cdot N^2)$ 。
空间复杂度: $O(T \cdot N^2)$ 。我们需要存储 dp 数组和 prefix_sum_dp 数组，它们的大小都是由最大时间、总朋友数决定的。

知识点总结

这道题是一道非常棒的计数DP练习题，喵~ 从中我们可以学到：

问题转化: 学会将一个关于排列组合的复杂问题，通过分析其内在约束，转化为一个更纯粹的计数问题。抓住“不关心个体，只关心数量”的核心是关键！
DP状态设计: 对于序列计数问题，DP状态通常需要包含当前位置、以及一些足以推导出后续状态的累积信息（如此处的总祝福数和上一时刻的祝福数）。
前缀和优化DP: 当DP转移方程中出现对某个变量在连续区间上的求和时，要立刻想到前缀和优化！这是将 $O(N)$ 转移降为 $O(1)$ 的常用技巧，能让你的代码跑得飞快，喵~
Pull vs. Push DP: 我们这里用了 Pull DP（计算当前状态，从之前的状态拉取信息），这种方式在需要区间求和时，往往比 Push DP（更新未来状态）更容易看出优化点并实现。

希望这篇题解能帮到你，祝大家刷题愉快，天天AC，喵~！(＾• ω •＾)

Birthday Reminders - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

DP状态设计 ​

DP转移方程 ​

复杂度与优化 ​

最终答案 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​