记录116#includebits/stdc.h using namespace std; long long last[130],dp[130];//last存储上一个位置结尾时各余数0到p-1对应的子串数量 //dp存储当前位置结尾时各余数对应的子串数量 int main(){ int p;//判断是p的倍数 string s;//数字串s cinps;//输入 int lens.size();//得到长度 long long ans0;//ans用于累计亲朋数的总数 for(int i0;ilen;i){//遍历字符串的每个位置处理以位置i结尾的所有子串 memset(dp,0,sizeof(dp));//清空当前dp数组准备重新计算以位置i结尾的状态 int nums[i]-0;//将当前字符转换为数字 dp[num%p];//单独考虑只包含当前字符的子串这个子串的余数是num%p所以对应余数的计数加1 for(int j0;jp;j){//考虑将当前数字拼接到之前所有子串的末尾 if(last[j]) dp[(j*10num)%p]last[j];//last[j]表示以上一个位置结尾、余数为j的子串数量 }//当我们在这些子串后面添加数字num时新的数值相当于原来的数值×10 num,因此新的余数是 (j * 10 num) % p ansdp[0];//dp[0] 表示以当前位置i结尾、且是p的倍数的子串数量 for(int j0;jp;j) last[j]dp[j];//将当前状态复制到last数组为下一次迭代做准备 } coutans;//输出 return 0;//结束程序 }前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。题目传送门https://www.luogu.com.cn/problem/P10262突破口给定一串长度为 L、由数字 0∼9 组成的数字串 S。容易知道它的连续子串共有 2L(L1)/2​ 个。如果某个子串对应的数允许有前导零是 p 的倍数则称该子串为数字串 S 对于 p 的亲朋数。例如数字串 S 为“ 12342 ”、p 为 2则在 15 个连续子串中亲朋数有“ 12 ”、“ 1234 ”、“ 12342 ”、“ 2 ”、“ 234 ”、“ 2342 ”、“ 34 ”、“ 342 ”、“ 4 ”、“ 42 ”、“ 2 ”共 11 个。注意其中“ 2 ”出现了 2 次但由于其在 S 中的位置不同记为不同的亲朋数。现在告诉你数字串 S 和正整数 p 你能计算出有多少个亲朋数吗这道题是一道非常经典的动态规划DP结合数论同余的题目。它的核心难点在于数据范围很大字符串长度可达 106106 如果暴力枚举所有子串并判断是否能被 pp 整除时间复杂度会达到 O(L2)O(L2) 绝对会超时。因此解题的关键在于利用“余数的传递性”在 O(L×p)O(L×p) 的时间内解决问题。下面我将为你拆解背后的逻辑并对代码进行逐行深度解析。 核心思路与知识点拆解1. 核心知识点同余定理模运算性质题目要求判断一个数字串是否是 pp 的倍数实际上就是判断这个数字对 pp 取模是否等于 0。假设我们有一个数字 AA 它对 pp 取模的余数是 jj 即 A≡j(modp)A≡j(modp) 。如果在 AA 的末尾拼接一个新的数字 numnum 形成的新数字就是 A×10numA×10num 。根据模运算规则新数字的余数为(A×10num)(mod p)((A(mod p))×10num)(mod p)(j×10num)(mod p)2. 动态规划逻辑我们不需要知道子串具体的数值是多少只需要知道以当前位置结尾的所有子串它们的余数分布情况。状态定义dp[r]表示以当前字符结尾的所有子串中模 pp 余数为 rr 的子串个数。状态转移情况一新开一个子串只包含当前字符s[i]的子串。它的余数就是s[i] % p。情况二接在旧子串后面将以s[i-1]结尾、余数为 jj 的所有子串后面都接上s[i]。根据上面的公式这些新子串的余数会变成(j * 10 num) % p。代码分析#includebits/stdc.h using namespace std;解析引入万能头文件包含所有标准库并使用标准命名空间。long long last[130], dp[130]; // last存储上一个位置结尾时各余数0到p-1对应的子串数量 // dp存储当前位置结尾时各余数对应的子串数量解析这里使用了滚动数组的思想。因为计算位置i的状态只需要位置i-1的状态所以不需要开二维数组dp[1000000][130]只需要两个一维数组交替使用即可极大地节省了空间。数组大小设为 130 是因为题目约定 p≤128。使用long long是因为子串总数约为 L2/2L2/2 当 L10^6 时结果会超过int的范围约 5×10^11 必须用长整型。int main(){ int p; // 判断是p的倍数 string s; // 数字串s cin p s; // 输入 int len s.size(); // 得到长度 long long ans 0; // ans用于累计亲朋数的总数解析读取模数 p 和数字串 s 获取长度并初始化答案ans为 0。for(int i 0; i len; i){ // 遍历字符串的每个位置处理以位置i结尾的所有子串 memset(dp, 0, sizeof(dp)); // 清空当前dp数组准备重新计算以位置i结尾的状态 int num s[i] - 0; // 将当前字符转换为数字解析外层循环枚举子串的结束位置i。memset将当前轮的dp数组清零因为我们要重新统计以s[i]结尾的余数分布。s[i] - 0是 C 中将字符数字如 3转换为整型数字3的标准写法。dp[num % p]; // 单独考虑只包含当前字符的子串这个子串的余数是num%p所以对应余数的计数加1解析这是状态转移的第一部分。以s[i]结尾的子串中有一种特殊情况是长度为 1 的子串即它自己。这个子串的值就是num它的余数自然是num % p所以该余数的计数加 1。for(int j 0; j p; j){ // 考虑将当前数字拼接到之前所有子串的末尾 if(last[j]) dp[(j * 10 num) % p] last[j]; // last[j]表示以上一个位置结尾、余数为j的子串数量 } // 当我们在这些子串后面添加数字num时新的数值相当于原来的数值×10 num, // 因此新的余数是 (j * 10 num) % p解析这是状态转移的第二部分也是算法的核心。遍历上一轮以i-1结尾所有可能的余数j。last[j]记录了上一轮余数为j的子串有多少个。如果把这些子串后面都加上当前的数字num根据同余定理它们的新余数都会变成(j * 10 num) % p。所以我们将last[j]的数量累加到当前dp数组对应的新余数位置上。ans dp[0]; // dp[0] 表示以当前位置i结尾、且是p的倍数的子串数量解析题目要求统计所有是 pp 倍数的子串。余数为 0 即代表能被 pp 整除。dp[0]就是以当前位置i结尾的所有亲朋数的个数。我们将每一轮产生的亲朋数都累加到总答案ans中。for(int j 0; j p; j) last[j] dp[j]; // 将当前状态复制到last数组为下一次迭代做准备 }解析当前字符s[i]处理完毕后当前的dp数组就变成了下一轮循环的“上一轮状态”。将dp的值复制给last以便处理下一个字符s[i1]时使用。cout ans; // 输出 return 0; // 结束程序 }解析输出最终累计的亲朋数总数。补充≡ 这个符号是数学中的同余符号读作“同余于”。它最早是由德国大数学家高斯在1801年系统引入并使用的专门用来描述数论中的“同余”关系。结合你刚才问到的 DP 状态压缩问题我们可以这样通俗地理解它数学含义a ≡ b (mod m)的意思是整数 a 和整数 b 除以同一个正整数 m 后得到的余数是完全相同的。算法中的意义在编程和算法里这个符号完美对应了取模运算Modulo。你可以把它看作是计算机里的取余操作符%的数学表达形式。比如17 ≡ 5 (mod 6)意思就是 17 和 5 除以 6 的余数都是 5。在之前的 DP 题目中我们之所以能用dp[j]来压缩状态本质上就是利用了同余符号背后的逻辑只要两个巨大的数字对p取模后的余数相同即它们在数学上满足≡关系它们在 DP 转移中的后续表现就是完全一样的因此我们只需要记录那个小小的余数即可。