假设分成如下三段:
[1..i][i+1..j][j+1..n]
考虑中间那一段,设f[i]为前i位组成的数模q的值,pow[i]为$10^i$模q的值,那么有:
f[j]-f[i]*pow[j-i]=0
f[j]*pow[i]=f[i]*pow[j]
f[j]*inv(pow[j])=f[i]*inv(pow[i])
枚举i,j,若[j+1..n]是r的倍数,[1..i]是p的倍数,且f[j]*inv(pow[j])=f[i]*inv(pow[i])则可行。
注意特判前导零的情况,时间复杂度$O(n)$。
#include<cstdio>
#define N 1000010
int n,p,q,r,i,t,can1[N],can3[N],pow[N],f[N],inv[N],c[N];char a[N];long long ans;
int main(){
scanf("%d%d%d%d%s",&n,&p,&q,&r,a+1);
for(i=1;i<=n;i++)a[i]-='0';
for(i=1;i<=n;i++){
t=(t*10+a[i])%p;
if(!t&&(i==1||a[1]))can1[i]=1;
}
for(pow[0]=i=1;i<=n;i++)pow[i]=pow[i-1]*10%r;
for(t=0,i=n;i;i--){
t=(t+pow[n-i]*a[i])%r;
if(!t&&(i==n||a[i]))can3[i]=1;
}
for(pow[0]=i=1;i<=n;i++)pow[i]=pow[i-1]*10%q,f[i]=(f[i-1]*10+a[i])%q;
for(inv[1]=1,i=2;i<q;i++)inv[i]=1LL*(q-inv[q%i])*(q/i)%q;
for(i=1;i<=n;i++)f[i]=1LL*f[i]*inv[pow[i]]%q;
for(i=2;i<n;i++){
if(can3[i+1]){
if(can1[i-1]&&!a[i])ans++;
ans+=c[f[i]];
}
if(can1[i-1]&&a[i])c[f[i-1]]++;
}
return printf("%lld",ans),0;
}