首先，如果一个串可以被分割成两个串且这两个串均满足条件，那么这个串一定满足条件。
证明:$a=0(mod$ $m)$,$b=0(mod$ $m)$则$a*x+b*y=0(mod$ $m)$（显然）
那么我们只要统计有多少种满足情况的子串就可以了，设数目为$k$，然后方案数就是$2^k$
注意如果最后原串不满足条件就要输出0（显然原串不满足那么拆成的子串中至少有一个不满足该性质）
说了这么多，其实特别好写。。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans=0,len;
const int Mod=1e9+7;
int main(){
freopen("4421.in","r",stdin);
freopen("4421.out","w",stdout);
scanf("%d %d",&n,&m);
char ch;
while((ch=getchar())<'0' || ch>'9');
if((ch-'0')%m==0)ans=1;
len=ch-'0';
while((ch=getchar())>='0' && ch<='9'){
len=(len*10+ch-'0')%m;
if(len==0){
if(ans==0)ans=1;
else ans=ans*2%Mod;
}
}
printf("%d\n",len==0?ans:0);
return 0;
}
评论 (0)
