ALGORITHM NOTES阅读地图
6个主要章节
1段代码示例
5组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览6 节 · 展开选择

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

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 的六种方案也可以独立枚举：全红一种，一个白花块配三个红花有四种位置，再加两个白花块一种，共六种。这种小规模枚举是检查递推的好方法。

用组合计数独立验算

固定白花块数量为 j，它们占据 k×j 朵花，剩下 i-k×j 个红花块。把每个白花块缩成一个符号后，总共有 i-(k-1)×j 个位置，从中选择 j 个放白花块，因此方案数是组合数 C(i-(k-1)×j, j)。

把 j=0…floor(i/k) 的这些组合数相加，就得到另一种计数表达式。相邻白花块仍然能唯一恢复成固定大小的块，所以这里没有额外的分组选择。

i=6、k=3 红花块数 压缩后的符号数 方案数
j=0 6 6 C(6,0)=1
j=1 3 4 C(4,1)=4
j=2 0 2 C(2,2)=1

合计仍为 6。这个公式适合手算与小规模对拍，不是让每个查询重新枚举 j；主算法的线性 DP 加前缀和更适合本题多次查询。

为什么不能直接套“零钱组合数”的循环

常见的无序组合计数，会先枚举块类型，再递增枚举总长度。它强制按类型顺序加入元素，因此同一组块只计一次。

本题 k=3、i=4 有 RRRR、RB、BR 三种序列。若先完整处理红块，再处理白块，就只会得到“4 个红块”和“1 个红块加 1 个白块”两种组合，把 RB 与 BR 合并了。

本文代码外层按目标长度递增，内层比较末尾块类型，所以不同末尾顺序会分别计入。两种循环回答的是不同问题，不能仅凭它们看上去都是背包就互换。

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) 内，加一次就够了。

取模后的前缀和，不再具有大小顺序

为了看清回绕，暂用模数 7 做教学演示，取 k=1。长度 1、2、3 的实际方案数是 2、4、8，实际前缀和是 2、6、14，但保存的余数变成 2、6、0。

查询 [2,3] 时，(0-2+7)%7=5，与实际区间和 4+8=12 对 7 取模一致。余数下降不是计数变少，而是跨过了模数。

这意味着可以继续做模意义下的区间差，却不能在这个数组上用普通大小比较寻找“累计方案数第一次超过某阈值”的位置。读过 二分答案 后尤其要区分：真实累计值的单调性，不会自动保留在余数表示中。提交代码仍使用题目要求的 1000000007，不是示例中的 7。

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 负责生成每个长度的答案，前缀和负责复用这些答案。回到 算法练习路径 时，可以把它作为动态规划入门后的组合练习。