题解：P10262 [GESP样题 六级] 亲朋数

· · 题解

dp 方法有点难想，如果能力不够建议先写搜索再看题解。

DP 方法

我们定义 f_{i,j} 表示所有以 s_i 结尾的子串除以 p 的余数是 j 的子串的数量。

故此我们可以推出一个公式：f_j=f_{j-1}\times10+q，推理过程见下图（字有点丑，见谅）。

由于题目要求我们求出有多少字串是可以被 p 整除的，根据模运算的性质可以知道，当 f_{i,j}\bmod p=0 的时候，说明可以被整除。同时，模运算的性质也告诉了我们任何被模的数的结果始终是小于模数的，即 a \bmod b \equiv c 时 c<b。故此我们只需要统计出 f_{i,0} 的总数即可。

最后附上 AC 代码：

#include<bits/stdc++.h>
using namespace std;
long long dp[129],f[129],ans; //dp[i]为原题解意思
int p;
string s;
int main(){
    cin>>p>>s;
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        int q=s[i]-'0';
        q%=p;
        for(int j=0;j<p;j++) f[j]=dp[j],dp[j]=0; //枚举模数
        for(int j=0;j<p;j++) dp[(j*10+q)%p]+=f[j];
        dp[q]++;
        ans+=dp[0];
    }
    cout<<ans;
    return 0;
}