洛谷 P10262 亲朋数：C++ 动态规划解法详解

题目背景

给定一个长度为 L 的数字串 S，以及一个正整数 p。我们需要统计 S 中有多少个连续子串所表示的数值是 p 的倍数。注意，允许前导零，且不同位置的相同数字视为不同的子串。

数据范围方面，p 最大为 128，而字符串长度 L 可达 10^6。这意味着 O(L^2) 的暴力枚举必然超时，必须寻找更高效的算法。

解题思路

这道题的核心在于如何快速判断以当前位置结尾的子串是否能被 p 整除。如果我们直接计算每个子串的数值，不仅会溢出，而且效率极低。

观察发现，对于位置 i 的字符 c[i]，以它结尾的所有子串可以看作是以 i-1 结尾的子串向左延伸一位（即乘以 10 加上当前位），或者是单独由 c[i] 构成的新子串。

我们可以定义状态 f[r] 表示：在遍历到当前位置之前，所有已处理过的子串中，对 p 取模余数为 r 的数量。当我们处理下一个字符时，这些余数都会变成 (r * 10 + digit) % p。同时，当前字符本身也构成一个新的子串，余数为 digit % p。

由于 p 很小（<= 128），我们可以用一个大小为 p 的数组来维护这些余数的计数。每读入一个新字符，就更新一次这个数组。如果某个子串余数为 0，说明它能被 p 整除，我们将对应的计数累加到答案中。

这种方法的时间复杂度是 O(L * p)，空间复杂度是 O(p)，完全能够承受 L=10^6 的数据规模。

代码实现

下面给出完整的 C++ 实现。为了适应竞赛环境中的大整数运算需求，这里使用了 #define int long long 宏来防止中间结果溢出。

#include <bits/stdc++.h>
using namespace std;

// 竞赛常用技巧：将 int 定义为 long long，避免手动转换类型导致的溢出
#define int long long

const int N = 150; // p 的最大值略大于 128
int p, f[N], g[N], ans;
string s;

signed main() {
    // 优化 I/O 操作速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> p >> s;
    
    int len = s.size();
    // 在字符串前添加空格，使索引从 1 开始，方便与循环逻辑对应
    s = " " + s;

    for (int i = 1; i <= len; i++) {
        // 清空 g 数组，用于存储当前轮次的状态
        memset(g, 0, sizeof(g));
        
        
         ( j = ; j < p; j++) {
             (f[j] == ) ; 
            
            
             t = (j *  + s[i] - ) % p;
            g[t] += f[j];
        }
        
        
         single_rem = (s[i] - ) % p;
        g[single_rem]++;
        
        
        ans += g[];
        
        
        (f, g, (g));
    }

    cout << ans << endl;
     ;
}