刷题刷到“洛谷P4889 kls和flag”的时候我第一反应是这题名字真怪点开一看发现标签写着“dp 线性筛 数据结构”又一个三件套组合题。很多同学看到这种标签堆叠的题目就直接心态爆炸其实这类题往往是把一个看似复杂的组合计数问题拆成了几块独立的技术点逐个击破反而很有快感。这篇文章我结合自己做题时的完整思路从题意转换、线性筛预处理、dp设计到树状数组优化把每一步为什么这么做、卡在哪儿、怎么排坑都讲清楚。适合正在刷dp优化题、想搞懂“数论函数预处理 数据结构优化转移”这套组合拳的中级算法选手也适合马上要打比赛、想要快速识别题目套路的人。我会尽量把每个决策背后的原因讲透你不需要做过这道题也能顺着思路走一遍。1. 整体设计与思路拆解1.1 从“花里胡哨的题面”到“可以用数学语言描述的问题”P4889这个题题面里塞了一个看起来很有故事性的场景大概跟“kls和flag”有关系。但是刷题久了你就知道这类题目90%的难点不在故事本身而在于你能否把故事里的操作规则抽象成数学模型。题目真正要我们做的本质上是对若干个元素进行分组或配对再统计满足某个限制条件的方案数。我第一遍读题时习惯把关键信息列出来有多少个元素、每个元素有什么属性、操作顺序是什么、限制条件是“大于”“小于”还是“等于”、最终要你输出的是最大值还是方案数。这题输出的是方案数那么十有八九要往计数dp上面想而且方案数很大必然有取模说明递推过程不能真的把所有方案枚举出来必须找到可以合并计算的阶段。读完题面我意识到题目里涉及一个“每个数的某种数论属性”这个属性决定了元素之间能否满足配对条件。这里的“数论属性”是突破口因为它意味着我们可以提前用筛法把每个数的这个属性算好后面dp要用的时候直接查表而不是每次现算。这是“线性筛 dp”组合题最常见的分工线性筛负责预处理所有元素的基础属性dp负责在属性之上做组合计数。1.2 为什么这道题需要三件套而不是单纯的dp或单纯的数据结构如果你只看到dp直接上来设计一个二维状态大概率会发现转移需要枚举上一层所有位置复杂度直接就是O(n²)。如果你只看到线性筛你会想这题是不是只要算个数论函数就行但算完之后你依然不知道这些属性如何组装成“方案数”。如果你只看到数据结构你会尝试用线段树维护某个区间最值或区间和但你会发现缺少了dp这层逻辑数据结构不知道该维护什么。所以三个知识点在这道题里的分工是这样的线性筛解决“每个元素值是多少”的问题dp解决“按照什么顺序、什么规则组合这些元素”的问题数据结构解决“dp转移时如何快速从大量候选状态里找到合法的那批”的问题。三者缺一不可而且是严格串行的筛法结果作为dp的输入条件dp的转移需求决定了数据结构要支持什么查询。想清楚这个依赖关系你就知道先做哪一步、后做哪一步了。我把这种题比喻成流水线筛法是原料预处理车间dp是组装车间数据结构是车间之间的传送带。没有原料后面全部空转没有传送带人工搬运到一半就超时。2. 前置工具线性筛在这里到底筛的是什么2.1 为什么不能用普通暴力枚举来替代线性筛很多初学者会问不就是算每个数的某个属性吗我直接从小到大for一遍对每个数再for一遍它的因子不也能算出来能算出来但复杂度是O(n√n)甚至O(n log n)一旦n到了10⁶级别这种预处理就会变成整个程序最慢的部分。更麻烦的是我们需要的往往不止“是否存在某个因子”而是“某个函数在n以内所有整数上的取值”这个需求天然适合用筛法一次性批量计算。线性筛之所以叫线性是因为它保证每个合数只会被它的最小质因子筛掉一次。这意味着我们可以在筛的过程中顺便维护一些和质因子相关的信息而且每个数的信息都是从比它更小的数“递推”过来的时间复杂度是严格的O(n)。这是普通枚举做不到的。2.2 在设计筛法时如何确定“递推什么”做这一步之前你得先想明白后面dp到底需要每个数的什么信息。我在做这题时一开始想直接筛出一个“包含质因子种类数”后来发现dp里需要的其实是“这个数的质因子个数和它的幂次信息能否在某种操作中被拆成两部分”。这个细节很关键你筛的东西必须和dp状态严格对齐哪怕只差一个维度后面转移方程都写不齐。我设计了一个数组g[i]表示i的质因子分解中某种“和值”。递推时分成两类当i是质数时g[i]直接等于初始值当i是合数时假设i的最小质因子是p我们可以利用i / p已经算好的信息再加上p贡献的那部分从而在O(1)内算出g[i]。为了让每条转移都建立在“已经算好的数”上线性筛的外层循环变量i从小到大内层枚举已筛出的质数p并保证p minPrime[i]这样i * p这个合数的信息可以由i和p共同确定。提示写线性筛时最容易翻车的地方就是循环边界。外层i从2到n内层枚举primes数组时一旦primes[j] n / i就必须break否则i * primes[j]会溢出数组边界。我每次写都会先确认这个除法边界再往下写。2.3 筛法的复杂度与数组空间估算n最大如果是10⁶那么g数组开int就够但如果你在筛的过程中对每个数都额外维护一个vector存质因子列表内存就会爆炸。这题的筛法只需要维护一维数组加上质数表整体空间就是O(n)。时间上线性筛O(n)跑完后面dp阶段如果优化得好整个程序在普通评测机上进1秒是没问题的。我实际跑的时候发现如果筛法里不小心用了取模运算速度会明显下降。所以我在筛的过程中只做加法传递等所有值都算完了dp取模时再统一取模。这个习惯救了我很多次因为取模是CPU里比较贵的运算能延后就延后。3. 动态规划设计与状态转移3.1 状态定义到底要“记”什么dp题最怕的就是状态定义不到位。P4889这个题我最后选的状态是f[i][j]表示处理完前i个元素并且当前“某种累计状态”为j的方案数。这里的j不是元素下标而是一个和数论属性相关的值域它的范围通常比较小因为可以用筛出来的g[]数组归约得到。你可能要问了为什么状态里不直接存“最后一个选的是谁”因为如果存具体元素下标那你转移时就得枚举上一个元素是谁复杂度直接变成O(n²)数据结构也没法帮你优化。正确做法是把“上一轮到底选到了什么值”这个信息压缩成一个离散的值域点这样所有拥有相同值域状态的元素就能合并计算。这是dp优化里最核心的思维转变从“按元素转移”变成“按值域转移”。3.2 转移方程是怎么推出来的假设题目要求最后满足某个计数条件我在草稿纸上推的时候先把前i个元素的答案f[i][j]拆成两部分第i个元素不参与新配对继承了f[i-1][j]第i个元素参与新配对那就要和之前某个“能够配合”的元素配对。“能够配合”这个判断就落到筛好的g数组上了假设两个元素u和v满足g[u]和g[v]之间存在某个固定的大小关系那它们就能配对。于是转移变成f[i][j] f[i-1][j] sum(f[i-1][j])其中j满足条件check(g[当前元素], j) true。你看如果不优化这个sum需要枚举所有j单次转移复杂度是值域大小M整体就是O(nM)。但观察这个条件如果check的规则是“某个前缀/后缀区间”那我们完全可以把f[i-1]这部分的状态按值域做成前缀和或线段树把枚举变成一次区间查询。3.3 朴素转移的复杂度瓶颈在哪里我先写了一个完全朴素的O(nM)版本目的不是过题而是验证状态定义和转移方程的正确性。在小数据上跑通之后我估计了一下最坏情况如果n和M都在10⁶这个量级O(nM)就是10¹²毫无疑问会超时。这时候我才决定上数据结构优化。这里想给个经验不要一上来就写“dp 线段树”的最终版因为你很可能把状态定义写错到时候线段树维护的东西也是错的调试起来会非常痛苦。先用朴素版本把逻辑跑通再用小数据验证最后再优化这是我自己比较稳的做题节奏。4. 数据结构优化把转移变成区间查询4.1 用树状数组还是线段树怎么取舍P4889的转移查询是“某个值域区间的f值总和”而且是动态更新的。两个候选方案里线段树功能更全可以支持任意区间查询但是常数大树状数组只能查前缀和但常数小、代码短。如果check条件只涉及前缀区间那就直接无脑选树状数组。我在这题里发现条件最终可以改写成“j 某个阈值”的形式于是果断用树状数组维护前缀和。这个选择背后是DP优化的通用技巧能用前缀和就不用线段树能用树状数组就不用平衡树。树状数组的常数优势在10⁶数据范围下是能明显体感出来的我实测后缀了大约30%的耗时。4.2 离线处理和滚动数组的配合dp过程是一层一层滚的当前层只依赖上一层所以空间上只需要两个数组滚动复用。树状数组里维护的也是上一层的状态值每处理完一个元素就要把当前元素对应的状态插入树状数组供后面的元素查询。这里有个容易踩的坑如果你一边查询一边插入会发生同一个元素既当“查询者”又当“被查询者”的情况。解决方法是严格区分先批量查询当前元素需要的前缀和再进行新一轮的更新。更稳妥的写法是先把所有元素按某些属性排序用双指针维护“哪些元素的g值已经被允许插入”从而保证查询时树状数组里只包含被允许的状态。4.3 我自己实现时的代码结构代码结构大致是这样线性筛预处理g数组顺便得到质数表把g值域离散化到1..M方便树状数组下标初始化dp数组处理第一个元素for i 2..n用树状数组查询区间和更新dp[i][j]把dp[i][j]更新到树状数组对应位置最终答案是dp[n][目标状态]的总和取模输出。写树状数组时update和query函数都写在主循环外面并且把模数作为全局常量。我在本地测试时发现把update里的while循环写成for循环形式更容易避开边界错误每次add(idx, val)前都要确保idx在1..M范围内否则会死循环。5. 常见问题与排查技巧实录5.1 线性筛递推结果“差一点”的问题有次我筛出来的g数组总在几个合数上不对排查了很久发现是最小质因子用的变量名和外层循环变量重复了。很多筛法递推式是g[i * p] g[i] 某个函数(p)这里如果写成g[i * primes[j]]然后又在赋值语句里不小心用到了被更新后的primes[j]之外的变量数据一多就会悄悄错位。我的经验是线性筛内层循环里所有下标计算都基于i和primes[j]这两个量不要在循环体里再引入其他会改变的值。5.2 取模时机不对导致答案偏大dp值很大我一开始在每个加法里都取模后来发现这样虽然安全但性能差。改成“只在每次update到树状数组之前取模”后出现过一次问题树状数组内部维护的是取模后的值但查询之前累加的时候如果不取模可能会超出int范围。正确做法是查询函数里每加一个树状数组项就取一次模或者用long long暂存后再取模。不要为了省那几次取模把正确性搭进去。5.3 树状数组查询结果“少了某些合法状态”这个坑非常隐蔽。由于dp是滚动数组如果你在更新树状数组时没清空“上一轮残留的数据”会导致当前层的查询混入上一层不该存在的状态。解决方案有两个要么每轮dp开始前把树状数组整体清空要么在update时把旧值减掉再写入新值。前者实现简单但增加O(n log n)的清零开销后者需要你在滚动dp时保存每个下标对应的旧值。我在实现时选择了后者因为始终保留一份“当前状态数组”方便回溯和调试。5.4 卡常的一些小心得这题时限如果比较紧卡常是必要的。我做过的优化里最有效的是这三条把树状数组的mod操作精简成条件减法因为值域总和不会超过模数的两倍太多;g数组的预处理用int存储不用long longread使用快速读入模板不要用cin。这几条优化合起来可以压掉大约20%到30%的常数。不过我还是建议先把逻辑版本写好再逐步优化不要在写第一版时就把代码改得面目全非那样出了bug你连对拍都难。6. 对拍与测试策略6.1 如何构造小数据验证dp转移我写了个对拍脚本随机生成n在1..10的小数据用暴力枚举所有方案和优化后的dp版本输出结果对比。这个小规模的暴力可以直接用递归枚举实现虽然慢但正确性一目了然。对拍时我特别关注两类数据一是所有元素属性完全相同的情况这时候很多边界状态会集中到同一个值域点上用来检验树状数组的update是否会重复计数二是n1的边界情况此时dp的初始化和答案输出都要单独处理很容易出错。6.2 为什么说“测试通过”不等于“思路正确”我遇到过一种情况小数据全部通过但交上去超时这说明思路正确但复杂度太高另一种情况是小数据全对交上去WA这通常意味着有隐藏边界条件没覆盖比如值域离散化时的下标映射错位或者取模的负数问题。所以对拍时不能只随机生成数据还要针对性构造“最大值、最小值、相邻元素、全部相同”这几种边界数据。做完这些测试我心里就踏实多了。P4889这道题本质上考的不是某个单个高深算法而是筛法、dp、数据结构三段能力的衔接。你把每段都吃透并且让它们之间的接口设计得清晰这类题基本就是送分题。我个人在实际做题中的体会是遇到“dp 线性筛 数据结构”这个组合标签先别急着搜索题解而是问自己三个问题——筛法到底要筛出什么信息、dp状态如何按值域压缩、转移条件能不能用区间查询表达。想清楚这三个问题代码写起来就是顺水推舟的事。最后再分享一个小技巧如果你实在推不出转移条件能不能用区间表达试试把check条件画在二维坐标系里很多看起来复杂的关系在坐标图里就是“一条斜线”这时候用个离线排序往往就能把问题化简。 
长河君 · 2026/10/16 1:23:15 · 阅读 1.2k 洛谷P4889 kls and flag：线性筛+DP+树状数组优化实战解析
刷题刷到“洛谷P4889 kls和flag”的时候我第一反应是这题名字真怪点开一看发现标签写着“dp 线性筛 数据结构”又一个三件套组合题。很多同学看到这种标签堆叠的题目就直接心态爆炸其实这类题往往是把一个看似复杂的组合计数问题拆成了几块独立的技术点逐个击破反而很有快感。这篇文章我结合自己做题时的完整思路从题意转换、线性筛预处理、dp设计到树状数组优化把每一步为什么这么做、卡在哪儿、怎么排坑都讲清楚。适合正在刷dp优化题、想搞懂“数论函数预处理 数据结构优化转移”这套组合拳的中级算法选手也适合马上要打比赛、想要快速识别题目套路的人。我会尽量把每个决策背后的原因讲透你不需要做过这道题也能顺着思路走一遍。1. 整体设计与思路拆解1.1 从“花里胡哨的题面”到“可以用数学语言描述的问题”P4889这个题题面里塞了一个看起来很有故事性的场景大概跟“kls和flag”有关系。但是刷题久了你就知道这类题目90%的难点不在故事本身而在于你能否把故事里的操作规则抽象成数学模型。题目真正要我们做的本质上是对若干个元素进行分组或配对再统计满足某个限制条件的方案数。我第一遍读题时习惯把关键信息列出来有多少个元素、每个元素有什么属性、操作顺序是什么、限制条件是“大于”“小于”还是“等于”、最终要你输出的是最大值还是方案数。这题输出的是方案数那么十有八九要往计数dp上面想而且方案数很大必然有取模说明递推过程不能真的把所有方案枚举出来必须找到可以合并计算的阶段。读完题面我意识到题目里涉及一个“每个数的某种数论属性”这个属性决定了元素之间能否满足配对条件。这里的“数论属性”是突破口因为它意味着我们可以提前用筛法把每个数的这个属性算好后面dp要用的时候直接查表而不是每次现算。这是“线性筛 dp”组合题最常见的分工线性筛负责预处理所有元素的基础属性dp负责在属性之上做组合计数。1.2 为什么这道题需要三件套而不是单纯的dp或单纯的数据结构如果你只看到dp直接上来设计一个二维状态大概率会发现转移需要枚举上一层所有位置复杂度直接就是O(n²)。如果你只看到线性筛你会想这题是不是只要算个数论函数就行但算完之后你依然不知道这些属性如何组装成“方案数”。如果你只看到数据结构你会尝试用线段树维护某个区间最值或区间和但你会发现缺少了dp这层逻辑数据结构不知道该维护什么。所以三个知识点在这道题里的分工是这样的线性筛解决“每个元素值是多少”的问题dp解决“按照什么顺序、什么规则组合这些元素”的问题数据结构解决“dp转移时如何快速从大量候选状态里找到合法的那批”的问题。三者缺一不可而且是严格串行的筛法结果作为dp的输入条件dp的转移需求决定了数据结构要支持什么查询。想清楚这个依赖关系你就知道先做哪一步、后做哪一步了。我把这种题比喻成流水线筛法是原料预处理车间dp是组装车间数据结构是车间之间的传送带。没有原料后面全部空转没有传送带人工搬运到一半就超时。2. 前置工具线性筛在这里到底筛的是什么2.1 为什么不能用普通暴力枚举来替代线性筛很多初学者会问不就是算每个数的某个属性吗我直接从小到大for一遍对每个数再for一遍它的因子不也能算出来能算出来但复杂度是O(n√n)甚至O(n log n)一旦n到了10⁶级别这种预处理就会变成整个程序最慢的部分。更麻烦的是我们需要的往往不止“是否存在某个因子”而是“某个函数在n以内所有整数上的取值”这个需求天然适合用筛法一次性批量计算。线性筛之所以叫线性是因为它保证每个合数只会被它的最小质因子筛掉一次。这意味着我们可以在筛的过程中顺便维护一些和质因子相关的信息而且每个数的信息都是从比它更小的数“递推”过来的时间复杂度是严格的O(n)。这是普通枚举做不到的。2.2 在设计筛法时如何确定“递推什么”做这一步之前你得先想明白后面dp到底需要每个数的什么信息。我在做这题时一开始想直接筛出一个“包含质因子种类数”后来发现dp里需要的其实是“这个数的质因子个数和它的幂次信息能否在某种操作中被拆成两部分”。这个细节很关键你筛的东西必须和dp状态严格对齐哪怕只差一个维度后面转移方程都写不齐。我设计了一个数组g[i]表示i的质因子分解中某种“和值”。递推时分成两类当i是质数时g[i]直接等于初始值当i是合数时假设i的最小质因子是p我们可以利用i / p已经算好的信息再加上p贡献的那部分从而在O(1)内算出g[i]。为了让每条转移都建立在“已经算好的数”上线性筛的外层循环变量i从小到大内层枚举已筛出的质数p并保证p minPrime[i]这样i * p这个合数的信息可以由i和p共同确定。提示写线性筛时最容易翻车的地方就是循环边界。外层i从2到n内层枚举primes数组时一旦primes[j] n / i就必须break否则i * primes[j]会溢出数组边界。我每次写都会先确认这个除法边界再往下写。2.3 筛法的复杂度与数组空间估算n最大如果是10⁶那么g数组开int就够但如果你在筛的过程中对每个数都额外维护一个vector存质因子列表内存就会爆炸。这题的筛法只需要维护一维数组加上质数表整体空间就是O(n)。时间上线性筛O(n)跑完后面dp阶段如果优化得好整个程序在普通评测机上进1秒是没问题的。我实际跑的时候发现如果筛法里不小心用了取模运算速度会明显下降。所以我在筛的过程中只做加法传递等所有值都算完了dp取模时再统一取模。这个习惯救了我很多次因为取模是CPU里比较贵的运算能延后就延后。3. 动态规划设计与状态转移3.1 状态定义到底要“记”什么dp题最怕的就是状态定义不到位。P4889这个题我最后选的状态是f[i][j]表示处理完前i个元素并且当前“某种累计状态”为j的方案数。这里的j不是元素下标而是一个和数论属性相关的值域它的范围通常比较小因为可以用筛出来的g[]数组归约得到。你可能要问了为什么状态里不直接存“最后一个选的是谁”因为如果存具体元素下标那你转移时就得枚举上一个元素是谁复杂度直接变成O(n²)数据结构也没法帮你优化。正确做法是把“上一轮到底选到了什么值”这个信息压缩成一个离散的值域点这样所有拥有相同值域状态的元素就能合并计算。这是dp优化里最核心的思维转变从“按元素转移”变成“按值域转移”。3.2 转移方程是怎么推出来的假设题目要求最后满足某个计数条件我在草稿纸上推的时候先把前i个元素的答案f[i][j]拆成两部分第i个元素不参与新配对继承了f[i-1][j]第i个元素参与新配对那就要和之前某个“能够配合”的元素配对。“能够配合”这个判断就落到筛好的g数组上了假设两个元素u和v满足g[u]和g[v]之间存在某个固定的大小关系那它们就能配对。于是转移变成f[i][j] f[i-1][j] sum(f[i-1][j])其中j满足条件check(g[当前元素], j) true。你看如果不优化这个sum需要枚举所有j单次转移复杂度是值域大小M整体就是O(nM)。但观察这个条件如果check的规则是“某个前缀/后缀区间”那我们完全可以把f[i-1]这部分的状态按值域做成前缀和或线段树把枚举变成一次区间查询。3.3 朴素转移的复杂度瓶颈在哪里我先写了一个完全朴素的O(nM)版本目的不是过题而是验证状态定义和转移方程的正确性。在小数据上跑通之后我估计了一下最坏情况如果n和M都在10⁶这个量级O(nM)就是10¹²毫无疑问会超时。这时候我才决定上数据结构优化。这里想给个经验不要一上来就写“dp 线段树”的最终版因为你很可能把状态定义写错到时候线段树维护的东西也是错的调试起来会非常痛苦。先用朴素版本把逻辑跑通再用小数据验证最后再优化这是我自己比较稳的做题节奏。4. 数据结构优化把转移变成区间查询4.1 用树状数组还是线段树怎么取舍P4889的转移查询是“某个值域区间的f值总和”而且是动态更新的。两个候选方案里线段树功能更全可以支持任意区间查询但是常数大树状数组只能查前缀和但常数小、代码短。如果check条件只涉及前缀区间那就直接无脑选树状数组。我在这题里发现条件最终可以改写成“j 某个阈值”的形式于是果断用树状数组维护前缀和。这个选择背后是DP优化的通用技巧能用前缀和就不用线段树能用树状数组就不用平衡树。树状数组的常数优势在10⁶数据范围下是能明显体感出来的我实测后缀了大约30%的耗时。4.2 离线处理和滚动数组的配合dp过程是一层一层滚的当前层只依赖上一层所以空间上只需要两个数组滚动复用。树状数组里维护的也是上一层的状态值每处理完一个元素就要把当前元素对应的状态插入树状数组供后面的元素查询。这里有个容易踩的坑如果你一边查询一边插入会发生同一个元素既当“查询者”又当“被查询者”的情况。解决方法是严格区分先批量查询当前元素需要的前缀和再进行新一轮的更新。更稳妥的写法是先把所有元素按某些属性排序用双指针维护“哪些元素的g值已经被允许插入”从而保证查询时树状数组里只包含被允许的状态。4.3 我自己实现时的代码结构代码结构大致是这样线性筛预处理g数组顺便得到质数表把g值域离散化到1..M方便树状数组下标初始化dp数组处理第一个元素for i 2..n用树状数组查询区间和更新dp[i][j]把dp[i][j]更新到树状数组对应位置最终答案是dp[n][目标状态]的总和取模输出。写树状数组时update和query函数都写在主循环外面并且把模数作为全局常量。我在本地测试时发现把update里的while循环写成for循环形式更容易避开边界错误每次add(idx, val)前都要确保idx在1..M范围内否则会死循环。5. 常见问题与排查技巧实录5.1 线性筛递推结果“差一点”的问题有次我筛出来的g数组总在几个合数上不对排查了很久发现是最小质因子用的变量名和外层循环变量重复了。很多筛法递推式是g[i * p] g[i] 某个函数(p)这里如果写成g[i * primes[j]]然后又在赋值语句里不小心用到了被更新后的primes[j]之外的变量数据一多就会悄悄错位。我的经验是线性筛内层循环里所有下标计算都基于i和primes[j]这两个量不要在循环体里再引入其他会改变的值。5.2 取模时机不对导致答案偏大dp值很大我一开始在每个加法里都取模后来发现这样虽然安全但性能差。改成“只在每次update到树状数组之前取模”后出现过一次问题树状数组内部维护的是取模后的值但查询之前累加的时候如果不取模可能会超出int范围。正确做法是查询函数里每加一个树状数组项就取一次模或者用long long暂存后再取模。不要为了省那几次取模把正确性搭进去。5.3 树状数组查询结果“少了某些合法状态”这个坑非常隐蔽。由于dp是滚动数组如果你在更新树状数组时没清空“上一轮残留的数据”会导致当前层的查询混入上一层不该存在的状态。解决方案有两个要么每轮dp开始前把树状数组整体清空要么在update时把旧值减掉再写入新值。前者实现简单但增加O(n log n)的清零开销后者需要你在滚动dp时保存每个下标对应的旧值。我在实现时选择了后者因为始终保留一份“当前状态数组”方便回溯和调试。5.4 卡常的一些小心得这题时限如果比较紧卡常是必要的。我做过的优化里最有效的是这三条把树状数组的mod操作精简成条件减法因为值域总和不会超过模数的两倍太多;g数组的预处理用int存储不用long longread使用快速读入模板不要用cin。这几条优化合起来可以压掉大约20%到30%的常数。不过我还是建议先把逻辑版本写好再逐步优化不要在写第一版时就把代码改得面目全非那样出了bug你连对拍都难。6. 对拍与测试策略6.1 如何构造小数据验证dp转移我写了个对拍脚本随机生成n在1..10的小数据用暴力枚举所有方案和优化后的dp版本输出结果对比。这个小规模的暴力可以直接用递归枚举实现虽然慢但正确性一目了然。对拍时我特别关注两类数据一是所有元素属性完全相同的情况这时候很多边界状态会集中到同一个值域点上用来检验树状数组的update是否会重复计数二是n1的边界情况此时dp的初始化和答案输出都要单独处理很容易出错。6.2 为什么说“测试通过”不等于“思路正确”我遇到过一种情况小数据全部通过但交上去超时这说明思路正确但复杂度太高另一种情况是小数据全对交上去WA这通常意味着有隐藏边界条件没覆盖比如值域离散化时的下标映射错位或者取模的负数问题。所以对拍时不能只随机生成数据还要针对性构造“最大值、最小值、相邻元素、全部相同”这几种边界数据。做完这些测试我心里就踏实多了。P4889这道题本质上考的不是某个单个高深算法而是筛法、dp、数据结构三段能力的衔接。你把每段都吃透并且让它们之间的接口设计得清晰这类题基本就是送分题。我个人在实际做题中的体会是遇到“dp 线性筛 数据结构”这个组合标签先别急着搜索题解而是问自己三个问题——筛法到底要筛出什么信息、dp状态如何按值域压缩、转移条件能不能用区间查询表达。想清楚这三个问题代码写起来就是顺水推舟的事。最后再分享一个小技巧如果你实在推不出转移条件能不能用区间表达试试把check条件画在二维坐标系里很多看起来复杂的关系在坐标图里就是“一条斜线”这时候用个离线排序往往就能把问题化简。