记录116

#include<bits/stdc++.h>
using namespace std;
long long last[130],dp[130];//last存储上一个位置结尾时，各余数（0到p-1）对应的子串数量
//dp存储当前位置结尾时，各余数对应的子串数量
int main(){
	int p;//判断是p的倍数 
	string s;//数字串s 
	cin>>p>>s;//输入 
	int len=s.size();//得到长度 
	long long ans=0;//ans用于累计亲朋数的总数 
	for(int i=0;i<len;i++){//遍历字符串的每个位置，处理以位置i结尾的所有子串
		memset(dp,0,sizeof(dp));//清空当前dp数组，准备重新计算以位置i结尾的状态
		int num=s[i]-'0';//将当前字符转换为数字
		dp[num%p]++;//单独考虑只包含当前字符的子串：这个子串的余数是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
		ans+=dp[0];//dp[0] 表示以当前位置i结尾、且是p的倍数的子串数量
		for(int j=0;j<p;j++) last[j]=dp[j];//将当前状态复制到last数组，为下一次迭代做准备
	}
	cout<<ans;//输出 
	return 0;//结束程序 
}

---

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

---

题目传送门https://www.luogu.com.cn/problem/P10262

---

突破口

给定一串长度为 L、由数字 0∼9 组成的数字串 S。容易知道，它的连续子串共有 2L(L+1)/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。
假设我们有一个数字 A ，它对 p 取模的余数是 j （即 A≡j(modp)。
如果在 A 的末尾拼接一个新的数字 num ，形成的新数字就是 A×10+num 。
根据模运算规则，新数字的余数为：

(A×10+num)(mod p)=((A(mod p))×10+num)(mod p)=(j×10+num)(mod p)

2. 动态规划逻辑
我们不需要知道子串具体的数值是多少，只需要知道以当前位置结尾的所有子串，它们的余数分布情况。

• 状态定义：dp[r] 表示以当前字符结尾的所有子串中，模 p 余数为 rr的子串个数。
• 状态转移：
  • 情况一（新开一个子串）：只包含当前字符 s[i] 的子串。它的余数就是 s[i] % p。
  • 情况二（接在旧子串后面）：将以 s[i-1] 结尾、余数为 jj 的所有子串，后面都接上 s[i]。根据上面的公式，这些新子串的余数会变成 (j * 10 + num) % p。

---

代码分析

#include<bits/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 ，当 L=10^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[i+1] 时使用。

	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 转移中的后续表现就是完全一样的，因此我们只需要记录那个小小的余数即可。