在 动态规划两题 中，我们保存的是“最多能得到多少”。如果目标改成“合法方案一共有多少种”，状态依然可以按长度排列，但合并候选的方式就从取最大值变成了求和。

Codeforces 474D 很适合把这一步与 前缀和 连起来：先算每种长度有多少方案，再快速回答一段长度范围内的方案总数。

1. 先把问题分成两层

474D · Flowers 官方题目 的难度为 1700，官方标签为 dp，于 2026-09-07 核对。下面使用原创解释与自拟推演，不整段翻译题面。

把红花记为 R、白花记为 W。红花可以逐朵出现，白花按长度为 k 的块出现；相邻的白花块可以连在一起，因此连续白花段的长度可以是 k、2k、3k…。

每次查询给出 [a,b]，需要统计总长度在这个范围内的合法序列数量，结果对 1000000007 取模。t、k 和查询端点均不超过十万，其中 t 是查询数。

这里有两个任务：

层次 问题 工具
单点 长度恰好为 i 的方案有多少 计数 DP
区间 长度从 a 到 b 的方案加起来有多少 前缀和

如果每次查询都重新运行 DP，会重复计算相同长度。所有查询共享同一个 k，可以先读完查询，再一次性预处理到最大的右端点。

2. 从最后一个块推导状态

定义 ways[i]：总长度恰好为 i 的合法颜色序列数，保存其对模数的余数。

观察最后一个块，只会出现两种情况：

  • 最后是一个 R：去掉它，剩下长度为 i-1 的任意合法序列。
  • 最后是 k 个 W：去掉它，剩下长度为 i-k 的任意合法序列，前提是 i≥k。

因此，当 i<k 时只能接红花；当 i≥k 时，两类数量相加。

为什么连续白花不会重复计数

例如 k=2 时，WWWW 可以看成两个白花块。但算法不会把“分组动作”当作额外方案：从右向左每次固定去掉 k 个白花，拆法是唯一的。

更一般地，任何合法序列的末尾颜色都是确定的。红色结尾与白色结尾互斥；每一类去掉末尾块后，又与前驱序列一一对应。因此没有遗漏，也没有把同一个序列数两次。

为什么 ways[0] 必须等于 1

这里的 1 表示“空序列这一种方案”。当第一次拼出恰好 k 个白花时，它来自空序列接一个白花块；如果把 ways[0] 写成 0，这个合法方案就会消失。

这与 Cut Ribbon 中的 dp[0]=0 不矛盾：Cut Ribbon 保存段数，空方案用了 0 段；这里保存方案数量，空方案本身有 1 种。初始化必须服从状态含义。

3. 用 k=3 手算一次

把白花块暂记为 B=WWW。注意 B 的长度是 3，不是 1。

i ways[i] 计算方式或例子
0 1 空序列
1 1 R
2 1 RR
3 2 RRR、B
4 3 RRRR、RB、BR
5 4 ways[4]+ways[2]
6 6 ways[5]+ways[3]

RB 与 BR 是不同颜色序列，所以顺序必须计入。不能把题目改成只统计“红花块有几个、白花块有几个”。

长度 6 的六种方案也可以独立枚举：全红一种，一个白花块配三个红花有四种位置，再加两个白花块一种，共六种。这种小规模枚举是检查递推的好方法。

4. 用前缀和回答查询

定义 prefix[i] = ways[1] + … + ways[i]，每次相加后取模，并令 prefix[0]=0。这里有意不纳入空序列，因为官方查询下界至少为 1。

于是 [a,b] 的答案为 (prefix[b] - prefix[a-1] + MOD) % MOD。

仍取 k=3，查询 [3,6] 的答案为 2+3+4+6=15。前缀和只是加速相同的求和，不改变计数对象。

数组 第 0 项 表达的含义
ways 1 空序列有一种
prefix 0 尚未累计任何正长度

两个数组的边界不同，是这题很容易写错的地方。取模之后，较后位置的余数也可能更小，所以差值加一次 MOD 才能避免负数；两个余数都在 [0,MOD) 内，加一次就够了。

5. 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    constexpr long long MOD = 1000000007LL;

    int t, k;
    cin >> t >> k;
    vector<pair<int, int>> queries(t);
    int limit = 0;
    for (auto& [a, b] : queries) {
        cin >> a >> b;
        limit = max(limit, b);
    }

    vector<long long> ways(limit + 1, 0);
    vector<long long> prefix(limit + 1, 0);
    ways[0] = 1;
    for (int i = 1; i <= limit; ++i) {
        ways[i] = ways[i - 1];
        if (i >= k) ways[i] = (ways[i] + ways[i - k]) % MOD;
        prefix[i] = (prefix[i - 1] + ways[i]) % MOD;
    }

    for (const auto& [a, b] : queries) {
        cout << (prefix[b] - prefix[a - 1] + MOD) % MOD << '\n';
    }
}

设查询最大右端点为 M。预处理耗时 O(M)，每次查询 O(1)，总时间 O(M+t)；保存查询与两个数组的空间为 O(M+t)。

当 k>M 时，每个长度只有全红一种方案，仍能直接使用这段代码。当 k=1 时，两种块都是长度 1，但颜色不同，因此 ways[i]=2^i；不能因为长度一样就把两种选择合并。

6. 从通过样例到主动验证

建议至少检查三类情况：

  • k=1，用模意义下的 2^i 和等比求和独立检查答案。
  • k 大于所有查询右端点，此时答案应为 b-a+1。
  • 小长度枚举全部红白串，检查每段连续白花的长度是否为 k 的倍数，再与 DP 比较。

第三种方法直接检查颜色序列，而不是复写一遍相同递推，更适合发现状态解释错误。最后再覆盖端点十万、单点查询和发生模回绕的区间。

这题把两个已经学过的工具接到一起：DP 负责生成每个长度的答案，前缀和负责复用这些答案。回到 算法练习路径 时，可以把它作为动态规划入门后的组合练习。