东北师范大学 研三 MythCoffee 洛谷 2026.10.16DP确实是千题千面。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(L1)个。如果某个子串对应的数允许有前导零是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输入 #12 102输出 #15输入输出样例 #2输入 #22 12342输出 #211说明/提示样例 1 解释5 55个亲朋数分别10 1010、102 102102、0 00、02 0202、2 22。⬆️转载自洛谷题目思考首先这是一道递推或者是DP。其次都是其次。递推和DP的做法基本是一致的先想DFS。如果你打不出来DFS你就打不出来递推和DP暴论。那么考虑DFS的打法emmmm额枚举L和R即可好像根本用不上dfs……也就是for(l1;ln;l){for(r1;rn;r){hf(l,r);}}接下来我们想一下整个计算的大头是什么每一个L到R的数都要重复构造。对于S123456当我构建好 12345 之后只需要 12345*106 就能构造一个新的数。数位分离考点所以我可以用这样的公式来替代for(l1;ln;l){t0;for(r1;rn;r){ff*10int(s[r])-48;}}这样构造的时间就减少了。但是这个循环还是爆因为二重循环本身就不行。那么问题就来了二重循环都运行不了我怎么枚举所以就不要枚举啦。DP的忌讳就是事事亲力亲为都想得到正确的解。这是非常不对滴。压缩一定要压缩第一个要压缩的是f的求法。f需要保存全部吗肯定是不需要的。我只需要f对于p的余数即可。所以f(f*10int(s[r])-48)%p;k的余数k乘以10的话k的余数也同时乘以10。但是由于可能会超过除数所以还要重新取模一次。这是压缩的第一步。第二步很难直接想到。我的想法其实非常简单且丝滑f求完余数了那f就剩下0,1……p-1这p种可能了。以s[r]为结尾的数一共就p种可能。以s[r1]结尾还是p种可能。转移s[r]结尾如果取余之后是x那s[r1]结尾的数就是x10s[r1] 之前答案的十倍加上新数重新取余放回去。这样枚举lr就变成了统计r结尾p种可能。O(LP)。这种思想一般都叫什么哈希优化我朴素的理解就是答案要分类。01背包的分类是按照容量相同这道题是余数相同所以要放在一起处理。注意不要下意识打10万因为这个错了好多次10的6次方是100万。AC代码#includeiostream#includecstringusingnamespacestd;chars[1000010],c;longlongp,i,h0,l,r,f[1000010],dp[1000010],k;longlongans0;intmain(){cinp;scanf(%c,c);cin.getline(s,1000010);intlenstrlen(s);for(inti0;ilen-1;i){k(int(s[i])-48)%p;for(intj0;jp;j){f[j]dp[j];dp[j]0;}for(intj0;jp;j){dp[(j*10k)%p]f[j];}dp[k];ansdp[0];}coutans;return0;}