ABC164 D.Multiple of 2019

D.Multiple of 2019

Question

给一个字符串S，求有多少个子串在十进制下为2019的倍数。

Solution

前置知识：
$S\left[l\right]\left[r\right]\times 10^{l-r}=s\left[l\right]\left[k\right]-s\left[r\right]\left[k\right]$S[l][r]×10l−r=s[l][k]−s[r][k]
若 $S\left[l\right]\left[k\right]-S\left[r\right]\left[k\right]\equiv 0\left(modP\right)$S[l][k]−S[r][k]≡0(mod P)
$\because 10^{x}modP\ne 0$∵10xmod P​=0
$\therefore S\left[l\right]\left[r\right]modP=0$∴S[l][r] mod P=0
若 $S\left[l\right]\left[r\right]\equiv 0\left(modP\right)$S[l][r]≡0(mod P)
则 $S\left[l\right]\left[r\right]\times 10^{r-l}modP=0$S[l][r]×10r−l mod P=0

这道题再增加难度就是任意模数 $P$P了二不一定是 $2019$2019，上面证明了任意模数P非10的因子的情况下。
下面讲如何处理 $P$P为 $10$10的因子情况下 $:$:
从 $1$1到 $n$n遍历若一个数个位为 $10$10的因子，则前面的数肯定是 $10$10的倍数，所以前面的数被 $P$P取余一定为 $0$0。
对应的ABC158E

将题意转化为对2019求余为0的子串有多少个。求一个后缀模数数组，后缀数组取模后的数为 $i$i,后缀数组取模后为 $i$i的个数为 $M\left[i\right]$M[i]。
$i的贡献值=M\left[i\right]\ast \left(M\right[i]-1)/2$i的贡献值=M[i]∗(M[i]−1)/2这里可以转化为加法，加上之前已有的 $M\left[i\right]$M[i]之后再更新 $M\left[i\right]$M[i]，注意初始化 $M\left[0\right]=1$M[0]=1。

Code ABC164D

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 2019;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

char s[N];
int a[N],suf[N],n,M[2020];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s+1;
	int n=strlen(s+1);
	int cnt=0;int base=1;
	M[0]++;
	for(int i=n;i>=1;i--){
		a[i]=s[i]-'0';
		suf[i]=(suf[i+1]+a[i]*base)%mod;
		cnt+=M[suf[i]];
		M[suf[i]]++;
		base=base*10%mod;
	}
	cout<<cnt<<'\n';
	return 0;
}

Code2 ABC158E

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

char s[N];
int suf[N],cnt[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,p;cin>>n>>p>>s+1;
	int base=1;
	ll ans=0;
	if(10%p==0){
		for(int i=1;i<=n;i++){
			if((s[i]-'0')%p==0) ans+=i;
		}
	}else{
		cnt[0]++;
		for(int i=n;i>=1;i--){
			int j=s[i]-'0';
			suf[i]=(suf[i+1]+j*base)%p;
			ans+=cnt[suf[i]];
			cnt[suf[i]]++;
			base=base*10%p;
		}
	}
	cout<<ans<<'\n';
	return 0;
}