自动搬运

查看原文

来自洛谷，原作者为

	Jared ⎛⎝≥⏝⏝≤⎛⎝ 没拿钩不改签

搬运于2025-08-24 22:56:18，当前版本为作者最后更新于2024-07-22 14:31:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}