1. 项目概述与问题拆解信奥P1356“数列的整除性”这道题乍一看题目描述可能有点绕但本质上是一个经典的“子集和问题”的变种。很多刚接触动态规划或者深度搜索的同学一看到“任意放或-”可能会联想到枚举所有表达式但那样复杂度是指数级的对于信奥的数据规模肯定超时。我当年第一次做这题也卡了半天后来才想明白它的核心其实是一个关于“余数”的背包问题。题目说的是给你一个整数数列你可以在每两个数之间放加号或减号从而计算出一个表达式的值。现在问是否存在一种添加符号的方式使得最终表达式的值能被一个给定的整数k整除。注意这里k可能不是正数题目明确说了k可能为负数但整除性的判断只关心绝对值这点很关键后面会细说。为什么不能暴力枚举所有2^(n-1)种符号组合呢因为n最大可以到10000这个数字的指数级枚举是天文数字完全不可行。所以我们必须寻找更聪明的办法。这道题的巧妙之处在于它不关心表达式最终的具体数值只关心这个数值除以k的余数。我们的目标就是判断能否通过加减组合得到一个余数为0的结果。这立刻将问题从“求值”转化为了“状态可达性”问题也就是动态规划的经典领域。2. 核心思路从暴力搜索到动态规划2.1 暴力搜索的局限与启示我们先从最直观的想法开始。假设数列是[a1, a2, a3]k7。 我们可以构造的表达式有a1a2a3, a1a2-a3, a1-a2a3, a1-a2-a3。 我们计算每个表达式的值然后看是否能被7整除。当n3时只有4种情况手算都行。但当n很大时比如n10000我们需要检查2^9999种可能性这显然是不可能的。但是暴力搜索给了我们一个重要的启示无论我们怎么添加符号表达式的最终结果一定是由初始数列中的数通过加或减组合而成的。也就是说最终结果可以看作是S (±a1) (±a2) ... (±an)。我们的目标是让S % k 0。2.2 关键转化关注余数而非具体值既然只关心S除以k的余数我们是否可以只追踪余数可能出现的状态而不是具体的S值呢这就是动态规划DP的思想。我们定义dp[i][j]为一个布尔值true/false表示考虑前i个数a1到ai时是否存在一种添加符号的方式使得得到的表达式值除以k的余数等于j。这里有一个非常重要的细节余数j的范围。在数学中余数通常是非负的。例如-5除以7的余数我们不能说是-5而应该是2因为-5 7 * (-1) 2。所以我们需要对计算过程中可能出现的负数余数进行“归一化”将其映射到[0, k-1]的范围。这个操作在代码里就是(x % k k) % k它能保证无论x是正还是负最终都得到一个在0到k-1之间的余数。那么状态如何转移呢 假设我们已经处理完前i-1个数得到了所有可能的余数集合。现在考虑第i个数a[i]。 对于前i-1个数能达到的任意一个余数r加上第i个数a[i]我们可以得到一个新的表达式值其对应的新余数为(r a[i]) % k注意归一化。 同样如果我们选择减去第i个数a[i]那么新余数就是(r - a[i]) % k同样需要归一化。所以状态转移方程可以描述为 如果dp[i-1][r]为真那么dp[i][(ra[i])%k]和dp[i][(r-a[i])%k]也都为真。初始状态是什么考虑前0个数表达式为空我们可以认为其值为0。0除以k的余数就是0。所以dp[0][0] true其他dp[0][j]均为false。最终我们只需要看dp[n][0]是否为真就能判断是否存在满足条件的表达式。注意关于k为负数的处理题目明确k可能为负数但整除性只与k的绝对值有关。例如判断一个数能否被-7整除等价于判断它能否被7整除。所以在程序一开始我们可以直接取k abs(k)将问题统一为正数k来处理这样可以避免很多边界问题。这是本题一个非常关键的预处理步骤很多粗心的同学会在这里丢分。2.3 空间优化滚动数组我们定义的dp数组是二维的dp[i][j]。i最大是n10000j最大是k-1。虽然k的绝对值不超过10000但10000*10000的布尔数组在内存上约100MB可能勉强过关但在时间上不断进行大数组的拷贝赋值效率不高。仔细观察状态转移方程dp[i]的状态只依赖于dp[i-1]。这意味着我们不需要保存整个二维数组只需要两个一维数组一个表示上一行dp_prev一个表示当前行dp_curr在每轮循环中滚动更新即可。这能将空间复杂度从O(n*k)降到O(k)是一个非常重要的优化。3. 代码实现与逐行解析理解了思路我们来看C实现。我会提供两个版本的代码一个是直观的二维DP便于理解一个是优化后的滚动数组版本推荐使用。3.1 基础二维DP版本#include iostream #include vector #include cmath // 用于abs函数 #include cstring // 用于memset函数 using namespace std; int main() { int m; // 测试数据组数 cin m; while (m--) { int n, k; cin n k; vectorint a(n 1); // 让下标从1开始符合思维习惯 for (int i 1; i n; i) { cin a[i]; } // 关键预处理k取绝对值因为整除性只与模数的绝对值有关 k abs(k); // 一个特判如果k为0根据题目描述“k是一个整数”但数学上模0无定义。 // 实际上信奥数据保证不会出现k0的情况但为健壮性考虑可以处理。 // 如果k0那么我们要判断的是表达式的值本身是否为0。 // 这里我们假设k不为0按题目数据范围来。 if (k 0) { // 这里简单处理实际上需要判断所有数能否通过加减得到0是一个子集和问题。 // 鉴于题目数据我们暂且跳过认为k不为0。 cout Not divisible endl; continue; } // dp[i][j]: 考虑前i个数是否存在表达式余数为j // 第二维大小设为k因为余数范围是0到k-1 vectorvectorbool dp(n 1, vectorbool(k, false)); // 初始化前0个数表达式值为0余数为0 dp[0][0] true; // 遍历每一个数 for (int i 1; i n; i) { // 遍历所有可能的余数 for (int r 0; r k; r) { if (dp[i-1][r]) { // 如果前i-1个数能组成余数r // 当前数取正号 int new_r_pos ((r a[i]) % k k) % k; // 归一化余数 dp[i][new_r_pos] true; // 当前数取负号 int new_r_neg ((r - a[i]) % k k) % k; // 归一化余数 dp[i][new_r_neg] true; } } } // 输出结果 if (dp[n][0]) { cout Divisible endl; } else { cout Not divisible endl; } } return 0; }代码要点解析k abs(k);这是本题的第一个坑点。务必在开始DP前对k取绝对值统一处理。vectorvectorbool dp(n1, vectorbool(k, false));创建二维DP表。使用bool类型节省空间。注意第二维大小是k因为余数j的范围是0到k-1。初始化dp[0][0] true;表示一个数都不考虑时表达式值为0余数自然为0。双重循环外层遍历每个数字a[i]内层遍历所有可能的余数r。if (dp[i-1][r])只有当前一个状态可达时才基于它进行转移。((r a[i]) % k k) % k这就是余数归一化操作。(ra[i]) % k可能得到负数再加上一个k再模k就能保证结果在[0, k-1]之间。这是C中处理负数取模的惯用写法。最后检查dp[n][0]即考虑所有n个数后余数0是否可达。这个版本逻辑清晰但空间开销大。当n和k都接近10000时dp数组大小约为10000*10000个bool大约100MB可能会超过一些在线评测系统的内存限制通常是256MB或512MB虽然可能不超但效率不高。3.2 优化滚动数组版本推荐#include iostream #include vector #include cmath #include cstring using namespace std; int main() { int m; cin m; while (m--) { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) { // 下标从0开始更符合C习惯 cin a[i]; } k abs(k); // 特判k0根据题目实际数据通常不会出现但加上更安全 if (k 0) { // 寻找是否存在非空子集和为0这里简化处理直接输出Not divisible // 实际上对于k0问题变为子集和问题判断能否得到和0可以用DP解但非本题重点 cout Not divisible endl; continue; } // 使用滚动数组dp_curr[j]表示当前行考虑前i个数余数j是否可达 // dp_prev[j]表示上一行考虑前i-1个数余数j是否可达 vectorbool dp_prev(k, false); vectorbool dp_curr(k, false); // 初始化考虑前0个数只有余数0可达 dp_prev[0] true; for (int i 0; i n; i) { // 清空当前行状态 fill(dp_curr.begin(), dp_curr.end(), false); for (int r 0; r k; r) { if (dp_prev[r]) { // 对当前数a[i]进行加操作 int new_r (r a[i]) % k; if (new_r 0) new_r k; // 处理负数余数等价于 (new_r k) % k dp_curr[new_r] true; // 对当前数a[i]进行减操作 new_r (r - a[i]) % k; if (new_r 0) new_r k; dp_curr[new_r] true; } } // 滚动当前行变成下一轮的上一行 swap(dp_prev, dp_curr); } // 循环结束后dp_prev中存储的就是考虑所有n个数之后的状态 if (dp_prev[0]) { cout Divisible endl; } else { cout Not divisible endl; } } return 0; }优化点解析滚动数组只使用两个一维数组dp_prev和dp_curr空间复杂度从O(n*k)降为O(k)。fill(dp_curr.begin(), dp_curr.end(), false);在每一轮开始前清空当前状态数组。因为每一轮的状态都是基于上一轮全新计算出来的而不是累加。if (new_r 0) new_r k;这是另一种处理负数余数归一化的方法比((x%k)k)%k更直观易懂。因为C中%运算的结果符号与被除数相同(r - a[i]) % k可能为负加上一个k就能保证落在正数区间。由于k是正数加一次k足以保证new_r非负。swap(dp_prev, dp_curr);这是实现“滚动”的关键。本轮计算出的dp_curr在下一轮循环中就变成了“上一轮”的状态dp_prev。通过交换指针或内容避免了大规模的数据拷贝效率极高。实操心得负数取模的坑C中的取模运算%是“取余”运算其结果满足a b * (a/b) a%b并且a%b的符号与a相同。这与数学上的“取模”运算结果始终非负不同。例如-5 % 7在C中结果是-5而不是数学上期望的2。所以只要涉及到可能为负数的取模操作就必须手动进行归一化写成(x % k k) % k或x x % k; if(x0) xk;。这是做数论和DP题时非常高频的一个错误点务必养成习惯。4. 算法深入分析与边界情况4.1 为什么是“可行性”DP而不是“计数”DP有些同学可能会想题目不是问“是否存在”吗那我们是不是可以定义dp[i][j]为前i个数组成余数j的方案数理论上可以但没必要。因为这是一个“是否可达”的布尔问题我们只关心true/false。用布尔数组可以减少不必要的计算和内存占用。如果题目改为“有多少种方式”那就需要改成计数DP。4.2 关于k0的特判虽然题目数据可能保证k不为0但作为一个健壮的程序考虑边界情况是很好的习惯。如果k0那么“除以k的余数”在数学上是没有定义的。此时题目的真实意图是判断表达式的值本身是否为0。这就变成了另一个经典问题给定一个数列能否通过添加/-号使表达式值为0这等价于问能否找到数列的一个非空子集其和为0这是一个NP难问题但对于n10000无法用简单DP解决。好在信奥原题数据应该规避了k0所以我们的特判直接输出Not divisible或进行更复杂的0-1背包判断目标和为0都是可以的但为了代码简洁和聚焦核心通常按前者处理。4.3 时间复杂度与空间复杂度分析时间复杂度我们有两层循环。外层循环遍历n个数内层循环遍历k个余数状态。对于每个(i, r)状态我们进行常数次操作判断、计算新余数、赋值。因此总时间复杂度为O(n * k)。 在最坏情况下n10000, k10000操作次数约为1亿次10^8。在C中1亿次简单的布尔运算和取模运算通常在1秒左右处于时间限制的边界上但一般可以接受。如果时间卡得特别紧可能需要进一步优化例如使用bitset。空间复杂度二维DP版本O(n * k)在极限数据下约100MB。滚动数组版本O(k)约10000个布尔值可以忽略不计。强烈推荐使用滚动数组版本。4.4 使用bitset进行极致优化当k比较大比如上限10000时内层循环for (int r0; rk; r)的10000次迭代是主要开销。我们可以利用C STL中的bitset来加速。bitset在内部以位bit为单位存储布尔值并且支持高效的位运算。思路是将dp_prev和dp_curr从vectorbool换成bitsetmaxK。状态转移可以通过位运算来实现dp_curr (dp_prev a[i]) | (dp_prev a[i])。 但这里有个问题我们的操作是模k的加减不是简单的移位。bitset的移位是循环移位吗不是它是逻辑移位。所以我们需要自己实现模k下的“循环左移”和“循环右移”。实际上我们可以这样操作将dp_prev左移a[i]位相当于所有可达余数r变成了(r a[i]) % k不对bitset左移是r a[i]会超出k的范围不是取模。因此不能直接用移位来模拟加法和取模。我们需要分别计算加a[i]和减a[i]后的新状态然后合并。虽然bitset的位运算很快O(k/word_size)但为了实现模k的加减我们需要对bitset进行“旋转”操作这需要额外的计算。对于k10000使用bitset可能带来的加速与实现的复杂性需要权衡。在信奥竞赛中O(n*k)的滚动数组DP通常已经足够通过本题。bitset优化更适用于k更大但状态仍可用位表示或者需要处理多组数据且时间非常紧张的场景。这里提供一个概念性的伪代码思路bitset10005 dp_prev, dp_curr, tmp; dp_prev.set(0); // 初始化余数0可达 for(int i0; in; i){ dp_curr.reset(); // 模拟加法: (r a[i]) % k tmp (dp_prev a[i]) | (dp_prev (k - a[i])); // 这是一个近似需要仔细处理边界 dp_curr | tmp; // 模拟减法: (r - a[i]) % k tmp (dp_prev a[i]) | (dp_prev (k - a[i])); dp_curr | tmp; dp_prev dp_curr; }注意上面的bitset移位操作并不是正确的模k加减实现因为bitset的和会移出边界而我们需要的是循环移位。C标准库的bitset不直接支持循环移位需要自己拼接实现代码会稍显复杂。因此对于初学者掌握滚动数组的DP写法就完全足够了。5. 常见错误与调试技巧在实现这道题时我见过学生们踩过各种各样的坑。下面列出一个清单帮你快速排雷。常见错误错误现象或原因解决方案忘记对k取绝对值当k为负数时数组维度dp[k]会出错或者余数计算混乱。在输入k后立即执行k abs(k)。负数取模未归一化使用(r - a[i]) % k直接作为数组下标导致访问越界下标为负。对所有取模结果进行归一化int new_r (x % k k) % k;或x x % k; if(x0) xk;。数组大小定义错误dp数组第二维开小了例如开了dp[n1][k]但k可能为0虽然数据可能没有。或者滚动数组版本dp_prev和dp_curr初始化大小为k但k可能为0。在取完abs(k)后如果k0进行特判。否则确保数组大小为k。滚动数组未清空当前状态在每一轮循环中直接使用dp_curr在上一次的值进行或操作导致状态错误累加。在每轮内层循环开始前用fill或assign将dp_curr全部置为false。初始化错误只初始化了dp[0][0]true但滚动数组版本中dp_prev和dp_curr在每一组数据前没有正确重置。对于每组数据在DP开始前确保dp_prev所有元素为false然后设置dp_prev[0]true。误用“计数DP”思路用int数组存储方案数最后判断dp[n][0]0。虽然结果可能正确但增加了计算复杂度和溢出风险。明确本题是“存在性”问题使用bool数组或bitset。时间复杂度估计错误使用了未优化的二维DP且n和k都很大导致程序运行超时。使用滚动数组优化空间如果还超时考虑k是否可能特别大或者检查是否有冗余循环。调试技巧小数据测试自己构造小的测试案例。例如n3, k7, a{1,2,3}。手算所有8种表达式看结果是否与程序输出一致。打印DP表对于二维DP版本可以在每轮循环后打印出dp[i]数组观察状态是如何传播的。这能帮你直观理解算法。关注边界测试k1任何数都能被整除应输出Divisible测试k等于数列和的情况测试包含负数的数列。使用静态局部变量对于滚动数组确保在每组测试数据开始时状态被正确重置。可以在循环开始时重新初始化vectorbool。6. 举一反三与相关题型P1356这道题是一个非常好的动态规划入门题它教会我们如何将“所有组合”的指数级问题通过关注“余数”这个关键状态转化为多项式时间可解的DP问题。掌握这个思想可以解决一大类类似问题。相关信奥/力扣题型子集和问题Partition Problem给定一个只包含正整数的数组判断是否可以分成两个和相等的子集。这就是k2目标和为总和一半的特殊情况也可以转化为类似的DP问题dp[i][j]表示前i个数能否组成和为j。目标和LeetCode 494给定一个整数数组和一个目标数给每个数前面添加或-求有多少种组合使得表达式值等于目标数。这几乎是本题的“计数版”将dp[i][j]的布尔值改为方案数即可。整除子集给定一个正整数集合找出最大的子集使得其中任意两个数之和、差、积都能被某个数整除。这类问题通常需要用到数论中关于最大公约数GCD的性质。模运算下的计数问题很多组合计数问题要求结果对某个大质数取模其递推关系也常常需要在模意义下进行状态设计和转移与本题有相通之处。核心思想提炼当题目涉及“所有组合”、“是否存在一种方式”时如果暴力枚举不可行就要思考最终结果是否只依赖于某个关键属性如余数、奇偶性、某一位的状态这个关键属性的可能取值是否有限能否定义dp[状态]来表示“是否可达”或“方案数”如果答案是肯定的那么动态规划很可能就是那把钥匙。最后关于信奥刷题我的个人体会是像P1356这样的题价值不在于一次AC而在于彻底理解其背后的状态压缩和转化思想。自己手动推导一下状态转移表用小的测试数据跟踪程序运行比单纯看题解代码要有效得多。遇到想不通的时候就回到最暴力的方法看看它和DP方法之间是怎么建立起联系的这个思考过程本身就是算法能力提升的关键。