Magic Numbers CodeForces - 628D - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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 ;

 }