AtCoder Beginner Contest 158 E.Divisible Substring

题目链接
思路：
设 $s_i$si​为 $[i,n]$[i,n]构成的十进制数。
若 $[l,r]$[l,r]构成的十进制数是p的倍数，则：
$\frac{s_l-s_{r+1}}{10^{n-r}}=0\left(modp\right)$10n−rsl​−sr+1​​=0  (mod  p)
如果 $gcd(10,p)=1$gcd(10,p)=1的话， $10^{x}modp$10x mod p是非零的,所以 $s_l-sr+1=0,modp$sl​−sr+1=0, mod p，即 $s_l=s_{r+1},modp$sl​=sr+1​, mod p
那么直接记录一下后缀的十进制表示%p后的值出现次数就可以了。
$gcd(10,p)!=1$gcd(10,p)!=1即p=2或5的时候，直接跑个dp就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,p;
char a[N];
LL vis[N];
LL f[N][10];
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>p>>a+1;
  if(p>=10){
    int pre=0;
    LL ans=0;vis[0]=1;
    LL c=1;
    for(int i=n;i>=1;i--,c=c*10%p){
      pre=(pre+(a[i]-'0')*c)%p;
      ans+=vis[pre];
      vis[pre]++;
    }
    cout<<ans<<'\n';
  }else{
    LL ans=0;
    for(int i=1;i<=n;i++){
      for(int j=0;j<p;j++){
        f[i][(j*10+a[i]-'0')%p]+=f[i-1][j];
      }
      f[i][(a[i]-'0')%p]++;
      ans+=f[i][0];
    }
    cout<<ans<<'\n';
  }

  return 0;
}