思路
以下纯考场思路。
今天模拟赛考到了这题的加强版，然后预处理写炸了，\(100\) 变成 \(70\)，当是给 CSP 攒 rp 了。
首先一眼看到题目可能会没有思路，没什么关系，手推一个暴力 DP，设 \(f_i\) 表示以 \(i\) 为结尾的划分方案数，显而易见的转移是：\(f_i=\sum_{j=1}^{i-1} f_j\)，其中满足 \(j\) 至 \(i\) 组成的数满足被 \(m\) 整除。
这个东西似乎难以被优化，所以考虑打几个特殊性质。
若 \(m=3\)，显然上述转移柿子满足的条件是 \(\sum_{k=j}^{i} a_k\) 是 \(3\) 的倍数，设原序列的前缀和数组为 \(sum_i\)，则此问题等价于 \(sum_i-sum_{j-1}\) 是 \(3\) 的倍数。
不妨根据除 \(3\) 的余数分类，显然 \(sum_i\) 若能它之前的 \(sum_j\) 转移过来必须满足它们除 \(3\) 的余数相同，而我们又可以据此推得若 \(sum_i\) 不是 \(3\) 的倍数，\(f_i\) 无法转移。
为什么呢，设 \(sum_i\) 除三的余数为 \(x\)，其中 \(x\) 不为 \(0\)，那么 \(x\) 从 \(i\) 之前的 \(x\) 转移过来，如此往前推，必将找到一个点 \(j\)，使得 \(j\) 前面不存在除 \(3\) 余数为 \(x\) 的数。
把这个东西推广一下，猜个结论，不难想到若 \(1\) 至 \(i\) 组成的数不是 \(m\) 的倍数，那么无法转移。
这个东西证明也与 \(3\) 的情况类似，不再赘述。
于是前缀和优化一下即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+10;
int const mod=1e9+7;
int sum[N],f[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
string s;cin>>s;s=" "+s;
sum[0]=f[0]=1;int res=0;
//这里 res 表示前 i 位除 m 的余数，我们的考试题限制了区间长度只能为 l~r，我没有加上 1~l 的部分，于是挂分，警示后人！
for (int i=1;i<=n;++i){
res*=10;res+=(s[i]-'0');res%=m;
if (!res) f[i]=sum[i-1];
sum[i]=(sum[i-1]+f[i])%mod;
}
cout<<f[n]<<'\n';
return 0;
}