P10262题解
fly_bamboo
·
·
题解
思路
这道题一眼就可以看出，是 O(l) 或 O(lp) 的时间复杂度,而求解字串是需要 O(l^2) 的时间的。
所以推断出这道题不能枚举字串。
这道题的突破点就在于 \bmod\ p。
动态规划 DP 可以吗？
可答案就非同一般了
我们用 `DP` 还是要枚举字串吗？
可以不用。
我们枚举每次子串的**个位**。
只用 $O(l)$ 的时间复杂度。
那么状态转移方程就轻而易举的出来了
注：这里我们用滚动优化，不然会被卡空间。
答案就是每次枚举后 $dp_0$ 的总和。
初始值：全部归 $0$。
枚举每次 $\bmod\ p$ 的结果即可。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p;
int dp[1000005],pre[1000005];
string s;
int num;
int ans=0;
signed main()
{
cin>>p>>s;
int len=s.size();
for(int i=0;i<len;i++)
{
num=(s[i]-'0')%p;
for(int j=0;j<p;j++) dp[j]=0;
for(int j=0;j<p;j++)
{
dp[(j*10+num)%p]+=pre[j];
}
dp[num]++;
for(int j=0;j<p;j++)
{
pre[j]=dp[j];
}
ans+=dp[0];
}
cout<<ans;
return 0;
}
```