1. 从赛场到复盘一份C国赛大题的个人实战拆解又到了每年这个时候各大编程竞赛的国赛阶段尘埃落定朋友圈里几家欢喜几家愁。我作为一枚在算法和工程领域摸爬滚打多年的老码农虽然早已过了亲自上阵打比赛的年纪但每年还是会习惯性地找来国赛题目尤其是C组的那些大题自己动手做一做权当是保持思维敏锐度的一种锻炼。今年也不例外趁着记忆还新鲜我把解题过程中的一些核心思路、代码实现上的取舍以及那些容易让人栽跟头的“坑点”整理出来。这不仅仅是一份“标准答案”更是一个从业者视角下的实战复盘希望能给正在备赛的你或是单纯对高性能C算法实现感兴趣的朋友提供一些不一样的参考。国赛级别的题目尤其是C组的大题往往不会只考察单一的语法知识点。它们更像是精心设计的综合项目把数据结构、算法设计、边界处理、代码效率乃至对计算机底层原理的理解全都打包在一起进行考验。你需要的不仅仅是将算法翻译成代码的能力更需要在时间压力和有限资源下做出最优技术选型的判断力。接下来我就以一道典型的、融合了动态规划、数论和高效IO处理的题目为例带你完整走一遍我的解题链路。2. 题目场景还原与核心矛盾分析我们假设一道虚构但极具代表性的国赛大题它融合了今年热词中“快速幂”、“大数处理”和“动态规划”的多个特征。题目大意如下给定一个长度为 N (1 ≤ N ≤ 10^5) 的整数数组 A和一个模数 M (1 ≤ M ≤ 10^97)。定义一种操作你可以选择数组中的一个连续子数组将其所有元素替换为该子数组所有元素的乘积对 M 取模后的值。你可以进行任意多次操作。请问最终整个数组可能得到的不同结果数组有多少种结果对 10^97 取模。第一眼看到题目矛盾点立刻浮现N 最大为 10^5如果暴力枚举所有子数组进行所有可能的操作序列复杂度是指数级的完全不可行。这迫使我们必须寻找问题背后的数学结构和规律。核心矛盾一操作的结合性与最终状态。仔细分析“操作”的定义它本质上是将一段区间“坍缩”成一个单点这个点的值是区间内所有元素乘积的模。这让人联想到区间合并问题。关键在于无论操作的顺序如何只要最终每个位置被“坍缩”的次数和范围决定了最终数组就是确定的。例如数组[a, b, c]如果先合并[a,b]变成[ab, c]再合并整个数组变成[abc]与直接合并整个数组的结果是一样的。这说明不同的操作序列可能对应同一种最终的“区间划分”方式。核心矛盾二模运算下的乘积与去重。由于结果要对 M 取模而 M 不一定是个质数题目只给了上限这带来了额外的复杂性。如果 M 是质数我们可以利用模逆元进行一些化简但 M 是任意的乘积可能因为模运算而产生“碰撞”即不同的原始乘积取模后得到相同的结果这会影响最终不同结果数组的计数。核心矛盾三状态空间的压缩。即使我们发现了问题可以转化为“区间划分”问题直接DP的状态定义也可能是dp[i][j]表示前 i 个元素经过操作后最后一个“块”的乘积模 M 为 j 的方案数。但 j 的可能取值有 M 种M 最大 10^97这显然无法承受。我们必须找到一种方法来压缩这个状态空间。我的突破口在于将注意力从“乘积的值”转移到“乘积的因子与模数的关系”上。因为一次操作是将区间乘积取模最终数组的每个位置本质上都是原数组某个前缀区间乘积的某种“剩余”。这里需要引入前缀积和模数分解的概念。3. 算法核心基于前缀积与GCD的动态规划设pre[i] (A[0] * A[1] * ... * A[i-1]) % M并定义pre[0] 1。那么对于任意一个最终状态假设它在位置 i 的元素是由原数组区间[l, r)坍缩而来那么这个元素的值就等于(pre[r] * inv(pre[l])) % M其中inv(x)表示 x 在模 M 下的逆元。但如前所述M 非质数时逆元不一定存在。这里的关键观察是最终数组的每个元素都必须能表示为pre[r] / pre[l]在模 M 意义下的值而这个除法成立的条件是pre[l]与 M 互质的部分可以被“抵消”。更精确地说令g gcd(pre[l], M)。那么pre[r]必须包含至少与pre[l]相同“质因子集合”相对于M的因子这个除法在模 M 下才有定义或者说才能找到一个整数 k 使得pre[l] * k ≡ pre[r] (mod M)。因此我们可以将状态与**最大公因数(GCD)**绑定。定义dp[i][g]表示考虑前 i 个元素当前最后一个“块”的起始位置的前缀积与 M 的最大公约数为 g 时所能形成的不同结果数组的个数这里的结果数组指的是从开头到 i 的这部分。状态转移方程推导 当我们处理到第 i 个元素0-indexed对应pre[i1]时我们有两种选择将A[i]并入前一个块。这要求前一个块的“g”能够整除pre[i1]相对于前一个起点的“增量”。实际上这相当于新的g gcd(g * A[i], M)。但更精确的转移是如果当前最后一个块的 GCD 状态是 g那么并入A[i]后新的状态g_new gcd(g * A[i], M)。方案数直接继承dp[i1][g_new] dp[i][g]。以A[i]开始一个新的块。那么新块的起始前缀积就是pre[i1]注意新块只包含A[i]时其值就是A[i] % M但用前缀积表示起点是pre[i]终点是pre[i1]该块的 GCD 状态初始为gcd(pre[i1], M)。但是为了状态定义一致我们定义新块时它的“g”是它的起点前缀积pre[i]与 M 的 gcd 吗不这会有问题。我们需要重新审视状态定义。更严谨的状态定义dp[i]是一个哈希表或数组如果g的状态可枚举dp[i][g]表示所有可能的结果数组中第 i 个位置所在的块其起点前缀积与 M 的最大公约数为 g 的方案数。注意这里的 g 描述的是“块起点”的性质而不是块本身的值。那么从dp[i]转移到dp[i1]延续当前块对于dp[i]中的每个状态(g, count)如果我们在位置 i 不划分那么位置 i1 的块起点不变因此起点前缀积的 gcd 仍然是 g。但是我们需要检查从 i 到 i1 这个元素能否并入这取决于当前块的实际值乘上A[i]后是否还能在模 M 下保持“合法性”。这等价于检查是否存在整数 x使得x * A[i] ≡ new_value (mod M)且gcd(x, M)与块的状态有关。这个检查非常复杂。鉴于上述复杂性竞赛中更常见的思路是转换视角。另一种经典的解法是注意到最终数组是原数组的一个“划分”每个划分块的值是块内乘积模 M。问题等价于有多少种划分方式使得相邻两个块的值不同因为如果两个相邻块值相同它们其实可以被合并成一个块而不改变最终数组。这样问题就变成了一个更清晰的 DP令f[i]表示前 i 个元素能形成的不同结果数组的个数。转移时我们枚举最后一个块的起点 j那么f[i] f[j-1]前提是区间[j, i]的乘积模 M 这个值没有在之前更近的、以 i 为结尾的块中出现过不这样仍然需要去重。实际上这是一个区间划分 DP 去重问题。我们可以用dp[i]表示以 i 结尾的所有划分方案数。dp[i] sum(dp[j-1])对于所有 j ≤ i且区间[j, i]的乘积模 M 在从 j 到 i 的“首次出现”位置就是 j我们需要保证对于同一个值只计算最靠左的划分点。最终我采用的是一种基于“最后出现位置”的线性 DP这也是处理这类“不同子序列”或“不同划分”问题的常用技巧。定义dp[i]: 考虑前 i 个元素能形成的不同结果数组的个数。last[val]: 记录乘积值val最近一次作为某个区间乘积出现时的区间左端点 L。注意不是出现的位置而是使得product(L, i) % M val的那个 L。转移方程dp[i] dp[i-1] * 2 - dp[last[cur_val] - 1]其中cur_val是从某个位置到 i 的区间乘积模 M。但我们需要枚举所有以 i 为结尾的区间吗那样又是 O(N^2)。这里需要第二个关键技巧利用前缀积和哈希表实现 O(N) 转移。我们维护一个前缀积prefix_product 1初始。遍历每个元素A[i]prefix_product (prefix_product * A[i]) % M。我们希望找到所有以 i 结尾的区间[j, i]的乘积它等于prefix_product * inv(prefix_product_before_j) % M。如果我们遍历所有 j就需要逆元且 M 可能非质数。换个思路我们维护一个哈希表map键是当前的前缀积prefix_product值是这个前缀积上一次出现时的 dp 值具体是dp[last_occur_index - 1]。当处理到 i 时当前的prefix_product记作cur。dp[i]可以由两部分组成所有从之前某个位置 j 开始的新块即划分点这对应于所有不同的前缀积值prev其数量不好直接算。实际上dp[i]可以从dp[i-1]推导而来。考虑前 i-1 个元素的所有方案dp[i-1]。对于每个方案我们在末尾添加第 i 个元素有两种方式a) 将A[i]单独作为一个新块。b) 将A[i]合并到前一个块中。方式 a) 对应方案数就是dp[i-1]因为每个原有方案后加一个单元素块得到新方案。方式 b) 对应方案数呢它等于前 i-1 个元素的方案中最后一个块可以吸收A[i]的那些方案数。这等价于前 i-1 个元素的方案其最后一个块的乘积值乘以A[i]模 M 后等于某个值。这很难直接计算。正确的 O(N) 动态规划 定义dp[i]为前 i 个元素的不同结果数组数。 定义sum[val]为所有以某个特定值val结尾的划分方案数之和。我们遍历 i 从 1 到 N计算当前前缀积s (s * A[i-1]) % M。dp[i] (dp[i-1] * 2) % MOD。这表示前 i-1 个元素的每个方案都可以通过将A[i-1]单独成块方案数继承或并入前一个块方案数也继承来扩展到 i。但这样计算了重复方案那些并入前一个块后使得前一个块的值变得和更早的某个块值相同的方案实际上在最终数组里是同一个结果。我们需要减去这些重复的方案。什么时候会重复当当前的前缀积s在之前某个位置j也出现过时。设上一次出现前缀积s的位置是j即pre[j] s。那么对于所有前j-1个元素的划分方案如果我们在j到i-1这个区间不进行任何划分即把这个长区间作为一个块那么形成的最终数组会和另一种划分方式重复即在前j-1个元素的某种划分后将[j, i-1]这个区间本身作为一个块其乘积模 M 为s * inv(pre[j]) % M 1不对应该是pre[i] / pre[j] 1因为pre[i] pre[j]。等等这里需要仔细推敲。更准确地说如果pre[i] pre[j]那么区间[j, i)的乘积模 M 为1。这意味着对于任何一种前j个元素的划分方案注意是前 j 个即索引 0 到 j-1如果我们把区间[j, i)作为一个整体块值为1得到的最终数组与另一种方案重复即在前j个元素的划分方案基础上将区间[j, i)中的每个元素都单独作为值为1的块因为每个单元素A[k]满足pre[k1]/pre[k] A[k]但乘积为1不意味着每个都是1。这个重复关系很微妙。经过推导和查阅类似题目如 Codeforces 上的某些题目最终的经典且正确的状态转移方程如下令dp[i]表示考虑前 i 个元素的不同结果数组数。 令sum[val]表示所有以值val作为最后一个块值的划分方案总数。 我们同时维护当前的前缀积cur 1。初始化dp[0] 1空数组有一种方案sum[0] 1最后一个块值是“空”或初始状态方案数为1这通常被解释为虚拟的起点cur 1。对于 i 从 1 到 Ncur (cur * A[i-1]) % M。dp[i] (dp[i-1] * 2 - sum[cur] MOD) % MOD。dp[i-1] * 2前 i-1 个元素的每个方案A[i-1]可以自成一块dp[i-1]也可以并入前一块dp[i-1]。sum[cur]需要减去重复的方案。sum[cur]表示在之前的所有划分中最后一个块的值恰好等于cur的方案数。为什么减去它因为如果当前我们将A[i-1]并入前一个块且并入后前一个块的新值变成了cur那么这种方案实际上等价于在某个更早的、最后一个块值已经是cur的划分方案后面加上一段乘积为1的区间即[j, i)。这些方案是重复的必须减去。sum[cur]就记录了这些“重复的祖先”方案的数量。更新sum[cur] dp[i-1]。因为对于下一个位置 i1 来说以 i 结尾的、最后一个块值为cur的新方案数就是dp[i-1]即所有前 i-1 个元素的方案后面接上一个值为cur的块这个块由A[i-1]单独形成或与前面合并形成但我们已经通过dp[i]的计算包含了合并的情况这里sum[cur]更新为dp[i-1]是经过推导的简化形式它表示“可以以cur作为新块结尾的方案基础数量”。这个算法的核心在于sum哈希表记录了每个可能的“最后一个块值”所对应的方案数并通过当前前缀积cur快速找到并减去那些会导致重复的方案。时间复杂度 O(N)空间复杂度 O(N M)但 M 可能很大哈希表只存储出现过的值所以实际是 O(N)。#include bits/stdc.h using namespace std; typedef long long ll; const int MOD 1e9 7; int solve(int N, vectorint A, int M) { vectorll dp(N 1, 0); dp[0] 1; // 空序列有一种方案 unordered_mapint, ll sum; // sum[val] 方案数 sum[0] 1; // 虚拟的“上一个块值”为0的方案数为1 ll cur 1; for (int i 1; i N; i) { cur (cur * A[i-1]) % M; dp[i] (dp[i-1] * 2 % MOD - sum[cur] MOD) % MOD; // 更新 sum[cur]。注意这里应该是加上 dp[i-1] 吗经典写法是 sum[cur] dp[i-1]。 // 但更常见的写法是 sum[cur] (sum[cur] dp[i-1]) % MOD 我们需要仔细分析。 // 实际上根据定义sum[cur] 应该更新为 dp[i-1]因为对于下一个i1来说 // 导致重复的“祖先”方案就是所有前i-1个元素的方案数对应A[i-1]单独成块值为 cur 的情况。 // 但A[i-1]并入前一个块的情况其新块值不一定是 cur这部分在 dp[i] 计算时通过减法处理了。 // 所以这里直接赋值即可。 sum[cur] dp[i-1]; } return dp[N]; }4. 实现细节、边界处理与性能优化上面的算法框架看似清晰但在实际的 C 竞赛实现中有大量的细节需要打磨否则极易出错或超时。4.1 模运算的陷阱题目要求结果对10^97取模但中间计算涉及对 M 取模。这两个模数不同必须严格区分。所有方案计数dp[i]和最终答案使用MOD 1e97。而计算前缀积cur以及作为哈希表键值时使用题目给定的M。const int MOD 1e9 7; // 结果取模用 int M; // 题目给定的操作取模数 ll cur 1; cur (cur * A[i-1]) % M; // 这里是对 M 取模 dp[i] (dp[i-1] * 2 % MOD - sum[cur] MOD) % MOD; // 这里是对 MOD 取模4.2 减法取模的防负处理dp[i] (dp[i-1] * 2 - sum[cur] MOD) % MOD;这是 C 中处理负数取模的标准做法。先加上 MOD再取模确保结果非负。4.3 哈希表的选择与优化unordered_mapint, ll在竞赛中通常足够快但如果想追求极致性能可以考虑以下两点如果 M 的范围较小比如 1e6可以直接使用vectorll数组代替哈希表以 O(1) 时间访问。但本题 M 可达 1e97数组开不下必须用哈希表。对于unordered_map预先调用reserve(N)预留足够空间可以减少 rehash 的次数提升性能。unordered_mapint, ll sum; sum.reserve(N 5); sum[0] 1;4.4 整数溢出的处理即使使用了long long在计算cur (cur * A[i-1]) % M时cur * A[i-1]仍可能溢出 64 位整数当 M 很大A[i] 也很大时。需要使用模乘法防止溢出cur (__int128_t)cur * A[i-1] % M; // C17 或更高版本使用 __int128 // 或者使用快速乘算法 ll mul_mod(ll a, ll b, ll mod) { ll res 0; a % mod; while (b) { if (b 1) res (res a) % mod; a (a * 2) % mod; b 1; } return res; } cur mul_mod(cur, A[i-1], M);4.5 初始化与边界条件dp[0] 1表示空数组有一种方案即不进行任何操作。sum[0] 1是一个技巧性的初始化。可以这样理解在开始之前我们认为存在一个“虚拟的最后一个块”其值为 0或一个不会出现的哨兵值且方案数为 1。这保证了当cur第一次出现某个值时sum[cur]为 0转移公式dp[i] dp[i-1]*2 - 0正确。4.6 测试与调试对于这类复杂 DP编写暴力解法用于小数据 N 10进行对拍是必不可少的。暴力解法可以枚举所有可能的操作序列虽然操作序列无限但本质是枚举所有区间划分用集合去重验证 DP 结果的正确性。5. 举一反三同类题型与变种思路这道题的核心考点在于利用前缀和/积哈希化将区间性质转化为前缀差性质并结合动态规划去重。这个技巧在竞赛中非常常见以下是一些变种可以帮助你巩固这个思想子数组和/积为定值的问题给定数组求有多少个子数组的和或积为 K。通常使用哈希表记录前缀和的出现次数一次遍历解决。不同子序列个数问题给定一个序列求其所有不同子序列的个数。经典 DPdp[i] dp[i-1]*2 - dp[last[a[i]]-1]其中last[x]记录字符 x 上一次出现的位置。这与我们本题的转移方程神似。带模数的区间合并计数问题本题的进阶版。如果操作不是替换为乘积而是替换为和、异或等思路类似但“重复”的定义会发生变化。例如对于区间和如果两个相邻块的和模 M 相同它们也可以合并但去重逻辑需要调整。结合数据结构优化如果题目条件更复杂比如对每次操作有代价要求总代价最小或最大时的方案数那么 DP 状态可能需要增加维度并使用线段树等数据结构来优化转移。在国赛级别的比赛中大题往往就是这些经典模型的复合或深度变形。平时练习时不能满足于 AC 一道题更要吃透其背后的问题转化思想如本题将操作序列转化为区间划分再将区间乘积转化为前缀积差、状态设计技巧如用哈希表存储以某个特征值结尾的方案数和去重方法如利用前缀历史信息减去重复贡献。6. 从解题到编码我的赛场时间分配建议如果你在真实的赛场上遇到这样的题目我建议按以下时间线推进前15分钟彻底读题用样例手动模拟确保完全理解操作定义和问题目标。在草稿纸上列举小规模数据N1,2,3的所有可能情况尝试寻找规律。这一步切忌想当然必须动手。接下来20分钟进行初步的算法构思。识别出这是计数问题大概率用 DP。尝试定义最朴素的状态如dp[i][j]分析其不可行性。然后寻找压缩状态的途径比如发现结果只与区间划分和块值有关进而想到前缀积和去重。这个阶段要大胆猜想小心验证。第35-60分钟推导出核心的 DP 转移方程。像我们上面那样一步步推理必要时引入辅助变量如sum哈希表。一旦方程在手立即用暴力程序对小数据验证。验证通过前不要急于写正解代码。第60-90分钟编写正式代码。注意模块化将核心 DP 部分、IO 部分分开。务必在写代码的同时处理边界条件和溢出问题。写完立刻用自己构造的小数据测试。最后30分钟进行全面的测试。包括随机小数据对拍、边界数据N1, N10^5元素全为1元素全为质数M 很小M 很大等、以及题目提供的样例。同时思考是否有未考虑到的 corner case如 M1 时所有数取模后都为0需要特殊处理吗在本题的算法中cur始终为0sum[0]的更新需要仔细处理可能需要对 M1 的情况特判因为所有cur都是0转移公式需要调整。注意在本题的算法中如果 M1那么cur恒为0。我们的初始化sum[0]1转移中dp[i] dp[i-1]*2 - sum[0]。这会导致dp[1] 2-11dp[2] 1*2-11... 最终dp[N]1。这符合直觉吗当 M1 时任何数取模后都是0所以无论怎么操作最终数组只能是全0数组只有1种可能。所以算法似乎能正确处理 M1。但为了安全在代码开头加一句if (M 1) { cout 1 endl; return; }也是好习惯。最后保持心态平稳。国赛大题通常都有难度能完全做对的人不多。清晰的思路、严谨的实现、稳定的发挥比死磕一道题更重要。即使没能完全解出写出正确的暴力解法并优化其中一部分也能获得可观的分数。