Magic Numbers CodeForces - 628D
dp函数中:pos表示当前处理到从前向后的第i位(从1开始编号),remain表示处理到当前位为止共产生了除以m的余数remain。
不一定要把a减一,也可以特判a自身,或者直接改记忆化搜索。
#include<cstdio>
#include<cstring>
#define md 1000000007
typedef long long LL;
LL m,d,ans1,ans2,len1;
LL ans[][][];
LL w[];
char c;
LL dp(LL pos,LL remain,bool pre0,bool limit)
{
if(pos>len1) return remain==&&pre0==;
if(!limit&&ans[pos][remain][pre0]!=-)
return ans[pos][remain][pre0];
LL i,res=,end=limit?w[pos]:;
for(i=;i<=end;i++)
if((pos%==&&i!=d)||(pos%==&&i==d))
res=(res+dp(pos+,(remain*+i)%m,pre0&&i==,limit&&i==w[pos]))%md;
return limit?res:(ans[pos][remain][pre0]=res);
}
int main()
{
LL i;
scanf("%I64d%I64d\n",&m,&d);
memset(ans,-,sizeof(ans));
scanf("%c",&c);
while(c!='\n')
{
w[++len1]=c-'';
scanf("%c",&c);
}
w[len1]--;
for(i=len1;i>=;i--)
{
if(w[i]>=) break;
w[i-]--;
w[i]+=;
}
ans1=dp(,,true,true);
memset(w,,sizeof(w));
len1=;
scanf("%c",&c);
while(c!='\n')
{
w[++len1]=c-'';
scanf("%c",&c);
}
ans2=dp(,,true,true);
printf("%I64d",(ans2-ans1+md)%md);
return ;
}