D. Flowers - 题解

比赛与标签

比赛: Codeforces Round 271 (Div. 2) 标签: dp 难度: *1700

题目大意喵~

主人，你好呀！今天我们来帮一只可爱的小土拨鼠解决晚餐问题，喵~

是这样的，这只小土拨鼠每顿晚餐都要吃一些红色（R）和白色（W）的花花。但是呢，它有个特别的口味：白色的花必须以 k 朵为一组连续地吃掉。比如说，如果 k=3，那么 (WWW) 就是一组合法的白花，但是 (W) 或者 (WW) 就不行啦。红花则没有限制，可以单独吃。

现在小土拨鼠想知道，如果要吃掉 a 到 b 朵（包含 a 和 b）花，一共有多少种不同的排列方式呢？因为答案可能会非常非常大，所以我们需要对 1000000007 取模哦。

输入格式：

• 第一行是两个整数 t 和 k，t 是询问次数，k 是白色花花必须凑成的数量。
• 接下来 t 行，每行是两个整数 a 和 b，代表一个询问的区间。

输出格式：

• 对每个询问 (a, b)，输出一行，表示吃掉 a 到 b 朵花的总方案数（模 1000000007）。

解题思路分析喵~

这道题看起来有点复杂，但别担心，让本猫娘来带你一步步拆解它，很快就能找到思路啦！

问题的核心是“求方案数”，这种问题通常都可以往**动态规划（DP）**的方向思考哦！

1. 状态定义

我们先来定义一个状态。一个很自然的想法是：dp[i] 表示吃掉恰好 i 朵花的所有合法排列方式有多少种。我们的目标就是求出 dp 数组，然后就能轻松回答所有询问了！

2. 状态转移方程

现在，我们来想一想 dp[i] 是怎么从之前的状态推导出来的呢？ 一个长度为 i 的合法花束，它的最后一朵（或者一组）花是什么呢？只有两种可能喵~

• 情况一：最后一朵是红花 (R) 如果我们在一个长度为 i-1 的合法花束后面添上一朵红花，得到的新花束长度为 i，并且肯定是合法的！因为红花没有限制嘛。所以，这种情况的方案数就是 dp[i-1]。

• 情况二：最后一组是 k 朵白花 (WW...W) 如果我们在一个长度为 i-k 的合法花束后面添上 k 朵白花，得到的新花束长度为 i，并且也肯定是合法的！因为白花必须是 k 朵一组出现。这种情况的方案数就是 dp[i-k]。当然，这只有在 i >= k 的时候才有可能发生哦。

这两种情况是互斥的（最后添加的花不一样），所以根据加法原理，我们可以把它们的方案数加起来！

于是，我们就得到了状态转移方程：

• 当 i < k 时，我们没法凑齐 k 朵白花，所以只能添加红花。dp[i] = dp[i-1]。
• 当 i >= k 时，既可以加红花，也可以加一组白花。dp[i] = (dp[i-1] + dp[i-k]) % MOD。

3. Base Case

任何DP都需要一个起点！dp[0] 代表吃 0 朵花，也就是一个空的花束。这本身就是一种方案，所以我们定义 dp[0] = 1。有了这个基础，我们就可以递推出所有的 dp[i] 啦！

4. 处理询问

题目要求的是 a 到 b 朵花的总方案数，也就是 dp[a] + dp[a+1] + ... + dp[b]。

如果每次询问都暴力求和，当 t 很大时，肯定会超时的说。这里有一个超级好用的优化技巧——前缀和！

我们可以预处理一个 prefix_sum 数组，prefix_sum[i] 表示 dp[1] + dp[2] + ... + dp[i] 的总和。 那么，dp[a] + ... + dp[b] 的值不就等于 prefix_sum[b] - prefix_sum[a-1] 了吗？这样每次询问都可以在 O(1) 的时间内解决啦！

注意喵： 在计算 (prefix_sum[b] - prefix_sum[a-1]) 时，结果可能是负数。为了保证结果是正数，我们可以使用 (prefix_sum[b] - prefix_sum[a-1] + MOD) % MOD 这个小技巧。

总结一下解题步骤：

1. 预处理 DP 数组：根据状态转移方程，计算出从 dp[1] 到 dp[100000] 的所有值。
2. 预处理前缀和数组：根据 DP 数组，计算出前缀和。
3. 回答询问：对于每个 (a, b)，利用前缀和数组，在 O(1) 时间内计算出结果并输出。

是不是感觉思路清晰多啦？喵~

代码实现喵~

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

// 这是解决 "D. Flowers" 问题的代码喵~
// 问题要求我们计算长度在 [a, b] 范围内的，由红花和白花组成的合法序列总数。
// 这里的限制是：白花必须以 k 朵为一组连续出现。
//
// 我们可以用动态规划来解决这个问题。设 dp[i] 为长度为 i 的合法花束序列的数量。
// 一个长度为 i 的合法序列可以通过两种互斥的方式构成：
// 1. 在一个长度为 i-1 的合法序列末尾添加一朵红花 ('R')。
//    这种情况的方案数是 dp[i-1]。
// 2. 在一个长度为 i-k 的合法序列末尾添加 k 朵白花 ('W...W')。这只有在 i >= k 时才可行。
//    这种情况的方案数是 dp[i-k]。
//
// 这就给了我们递推关系：
// - 当 i < k 时: dp[i] = dp[i-1]。因为 dp[0] = 1（空序列），这意味着对于 i < k，dp[i] = 1，因为只能是全红序列。
// - 当 i >= k 时: dp[i] = (dp[i-1] + dp[i-k]) % MOD。
//
// 由于有多次询问，但 k 是固定的，我们可以预先计算出 dp 数组直到最大可能的长度 (10^5)。
// 为了高效地回答关于区间 [a, b] 内方案总和的询问，我们使用前缀和数组。
// 设 prefix_sum[i] = (dp[1] + dp[2] + ... + dp[i]) % MOD。
// 那么对于一个询问 (a, b)，答案就是 (prefix_sum[b] - prefix_sum[a-1]) % MOD。
//
// 整体算法流程如下：
// 1. 读取询问次数 't' 和白花块大小 'k'。
// 2. 预计算 dp 数组到最大长度 10^5。
// 3. 根据 dp 数组预计算前缀和数组。
// 4. 对 't' 次询问中的每一次 (a, b)，利用前缀和数组计算结果并输出。
// 所有计算都在模 1000000007 下进行。

int main() {
    // 使用快速 I/O 来提升性能，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t, k;
    std::cin >> t >> k;

    const int MAX_LEN = 100000;
    const int MOD = 1000000007;

    // dp[i] 存储长度为 i 的合法花束序列的数量。
    std::vector<int> dp(MAX_LEN + 1);
    
    // Base Case: 长度为 0 的空序列有 1 种方式。
    dp[0] = 1;

    // 使用递推关系填充 DP 表。
    for (int i = 1; i <= MAX_LEN; ++i) {
        // 情况 1: 添加一朵红花。这可以接在任何长度为 i-1 的合法序列后面。
        dp[i] = dp[i-1];
        
        // 情况 2: 添加 k 朵白花。这可以接在任何长度为 i-k 的合法序列后面。
        if (i >= k) {
            dp[i] = (dp[i] + dp[i-k]) % MOD;
        }
    }

    // prefix_sum[i] 存储 dp[1] 到 dp[i] 的和。
    std::vector<long long> prefix_sum(MAX_LEN + 1, 0);
    for (int i = 1; i <= MAX_LEN; ++i) {
        prefix_sum[i] = (prefix_sum[i-1] + dp[i]) % MOD;
    }

    // 处理 t 次询问。
    while (t--) {
        int a, b;
        std::cin >> a >> b;
        
        // 使用前缀和计算长度在 a 到 b 之间的方案总数。
        // 公式是 (prefix_sum[b] - prefix_sum[a-1])。
        // 我们加上 MOD 再取模，是为了处理减法可能产生的负数，确保结果总是非负的。
        long long result = (prefix_sum[b] - prefix_sum[a-1] + MOD) % MOD;
        std::cout << result << "\n";
    }

    return 0;
}

复杂度分析

• 时间复杂度: O(MAX_LEN + t) 的说。

  • 我们需要一个 for 循环来预计算 dp 数组，这需要 O(MAX_LEN) 的时间。
  • 接着用另一个 for 循环计算前缀和数组，也需要 O(MAX_LEN) 的时间。
  • 最后，处理 t 个询问，每个询问都只需要 O(1) 的时间。
  • 所以总的时间复杂度就是预处理的 O(MAX_LEN) 加上处理询问的 O(t)，合起来就是 O(MAX_LEN + t) 啦！

• 空间复杂度: O(MAX_LEN) 的说。

  • 我们需要一个 dp 数组和一个 prefix_sum 数组来存储预计算的结果，它们的大小都和最大长度 MAX_LEN 成正比。所以空间复杂度是 O(MAX_LEN)。

知识点与总结

喵~ 这道题是不是很有趣呀？它完美地展示了动态规划和前缀和这对黄金搭档的威力！

1. 动态规划思想: 当一个大问题的解可以由小问题的解推导出来时，DP 就是我们的好朋友！关键在于找到正确的状态定义和状态转移方程。这道题的递推关系 dp[i] = dp[i-1] + dp[i-k] 是一个非常经典的线性 DP 模型。
2. 前缀和优化: 对于涉及大量区间和查询的问题，前缀和是一种极其高效的优化手段。一次预处理，终身（查询）受益！它能把每次查询的时间复杂度从 O(N) 降到 O(1)。
3. 模运算技巧: 在进行模运算时，尤其是减法，要记住 (a - b + MOD) % MOD 这个公式，防止出现负数导致结果错误哦！

掌握了 DP 和前缀和的组合拳，很多看起来棘手的问题都会变得迎刃而解啦！希望这篇题解能帮到主人，继续加油，向着更高的目标前进吧！喵~ >w<