企业官网建设流程全解析

东北师范大学 研三 MythCoffee 洛谷 2026.10.16

DP确实是千题千面。DP就像是师傅教的手艺一样，看感觉，看练，但只可意会不可言传。

P10262 [GESP样题 六级] 亲朋数

P10262 [GESP样题 六级] 亲朋数

题目背景

对应的选择、判断题：https://ti.luogu.com.cn/problemset/1106

题目描述

给定一串长度为L LL、由数字0 ∼ 9 0\sim 90∼9组成的数字串S SS。容易知道，它的连续子串共有L ( L + 1 ) 2 \frac{L(L + 1)}22L(L+1)​个。如果某个子串对应的数（允许有前导零）是p pp的倍数，则称该子串为数字串S SS对于p pp的亲朋数。

例如，数字串S SS为“12342 1234212342”、p pp为2 22，则在15 1515个连续子串中，亲朋数有“12 1212”、“1234 12341234”、“12342 1234212342”、“2 22”、“234 234234”、“2342 23422342”、“34 3434”、“342 342342”、“4 44”、“42 4242”、“2 22”共11 1111个。注意其中“2 22”出现了2 22次，但由于其在S SS中的位置不同，记为不同的亲朋数。

现在，告诉你数字串S SS和正整数p pp，你能计算出有多少个亲朋数吗？

输入格式

输入的第一行，包含一个正整数p pp。约定2 ≤ p ≤ 128 2 \leq p \leq 1282≤p≤128。
输入的第二行，包含一个长为L LL的数字串S SS。约定1 ≤ L ≤ 10 6 1 \leq L \leq 10^61≤L≤106。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

2 102

输出 #1

5

输入输出样例 #2

输入 #2

2 12342

输出 #2

11

说明/提示

样例 1 解释

5 55个亲朋数，分别10 1010、102 102102、0 00、02 0202、2 22。

⬆️转载自洛谷

题目思考

首先，这是一道递推或者是DP。

其次都是其次。

递推和DP的做法基本是一致的：先想DFS。如果你打不出来DFS，你就打不出来递推和DP（暴论）。

那么考虑DFS的打法，emmmm，额，

枚举L和R即可，好像根本用不上dfs……

也就是

for(l=1;l<=n;l++){for(r=1;r<=n;r++){h+=f(l,r);}}

接下来
我们想一下，整个计算的大头是什么：每一个L到R的数都要重复构造。
对于S=123456
当我构建好 12345 之后，只需要 12345*10+6 就能构造一个新的数。（数位分离考点）

所以我可以用这样的公式来替代：

for(l=1;l<=n;l++){t=0;for(r=1;r<=n;r++){f=f*10+int(s[r])-48;}}

这样构造的时间就减少了。但是这个循环还是爆，因为二重循环本身就不行。那么问题就来了

二重循环都运行不了，我怎么枚举？

所以就不要枚举啦。DP的忌讳，就是事事亲力亲为，都想得到正确的解。这是非常不对滴。
压缩！一定要压缩！

第一个要压缩的，是f的求法。f需要保存全部吗？肯定是不需要的。我只需要f对于p的余数即可。

所以：

f=(f*10+int(s[r])-48)%p;

k的余数，k乘以10的话，k的余数也同时乘以10。但是由于可能会超过除数，所以还要重新取模一次。
这是压缩的第一步。

第二步：很难直接想到。我的想法其实非常简单且丝滑：f求完余数了，那f就剩下0,1，……，p-1这p种可能了。

以s[r]为结尾的数，一共就p种可能。以s[r+1]结尾，还是p种可能。
转移！
s[r]结尾如果取余之后是x，那s[r+1]结尾的数，就是x10+s[r+1] 之前答案的十倍，加上新数，重新取余放回去。
这样，枚举lr就变成了统计r结尾，p种可能。O(LP)。

这种思想一般都叫什么哈希优化，我朴素的理解就是：答案要分类。

01背包的分类，是按照容量相同
这道题是余数相同，所以要放在一起处理。

注意，不要下意识打10万，因为这个错了好多次，10的6次方是100万。

AC代码：

#include<iostream>#include<cstring>usingnamespacestd;chars[1000010],c;longlongp,i,h=0,l,r,f[1000010],dp[1000010],k;longlongans=0;intmain(){cin>>p;scanf("%c",&c);cin.getline(s,1000010);intlen=strlen(s);for(inti=0;i<=len-1;i++){k=(int(s[i])-48)%p;for(intj=0;j<p;j++){f[j]=dp[j];dp[j]=0;}for(intj=0;j<p;j++){dp[(j*10+k)%p]+=f[j];}dp[k]++;ans+=dp[0];}cout<<ans;return0;}