Atcoder ABC E

Atcoder ABC E - Divisible Substring

题意

一个长为n(2e5)的数字串,给一个质数p（1e4），能被p整除的子串（连续）个数

思路

因为p是个素数，所以要想到用素数的条件。最朴素的就是dp[i][j]第i位为最低位modp余数是j的子串有多少个，但是转移是np的，我们可以仔细想一想，有什么状态时多余的，转移每次都要乘j10+s[i]-'0'这一个操作有没有意义呢？我们假设p和10互质，其实就是没有意义的，因为p如果和10互质那么对于每个数后面无论添加多少个0都不会改变它和p的整除情况。小证明：添加0就相当于对于一个乘（2*5）的质因数，而p没有2和5的质因数，所以就不会有影响。那么问题就转化成例如s[1]s[2]s[3]s[4]s[5]s[6] 如果s[4]s[5]能够被p整除，那么s[4]s[5]0也能被p整除，也就是说我们只要记录每一个后缀的膜p的余数，相同的两两组合即可。而对于后缀modp等于0的来说，还要额外加上单独取一个的。
记住，以上是基础p和10互质的情况，事实上大于10的素数肯定不和10互质，可以从唯一分解定理理解。而小于10的有2和5和10互质，只要考虑以2或者以5结尾的子串有几个，本题就解决了

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
char s[maxn];
ll dp[10000+5];

int main(){
	ll n,p;
	cin>>n>>p;
	cin>>(s+1);
	ll ans=0;
	if(p==2||p==5){
		for(int i=1;i<=n;i++){
			if((s[i]-'0')%p==0){
				ans+=i;
			}
		}
	}
	else {
		ll tmp=0;
		ll base=1;
		for(int i=n;i>=1;i--){
			tmp=(tmp+(s[i]-'0')*base)%p;
			base=(base*10)%p;
			dp[tmp]++;	
		}
		ans+=dp[0]+1ll*dp[0]*(dp[0]-1)/2;
		for(int i=1;i<=p-1;i++){
			ans+=1ll*(dp[i]-1)*dp[i]/2;
		}
	}
	cout<<ans;
	return 0;
}