Magic Numbers CodeForces - 628D

2018-06-17 21:49:46来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Magic Numbers CodeForces - 628D

dp函数中:pos表示当前处理到从前向后的第i位(从1开始编号),remain表示处理到当前位为止共产生了除以m的余数remain。

不一定要把a减一,也可以特判a自身,或者直接改记忆化搜索。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define md 1000000007
 4 typedef long long LL;
 5 LL m,d,ans1,ans2,len1;
 6 LL ans[2010][2010][2];
 7 LL w[2010];
 8 char c;
 9 LL dp(LL pos,LL remain,bool pre0,bool limit)
10 {
11     if(pos>len1)    return remain==0&&pre0==0;
12     if(!limit&&ans[pos][remain][pre0]!=-1)
13         return ans[pos][remain][pre0];
14     LL i,res=0,end=limit?w[pos]:9;
15     for(i=0;i<=end;i++)
16         if((pos%2==1&&i!=d)||(pos%2==0&&i==d))
17             res=(res+dp(pos+1,(remain*10+i)%m,pre0&&i==0,limit&&i==w[pos]))%md;
18     return limit?res:(ans[pos][remain][pre0]=res);
19 }
20 int main()
21 {
22     LL i;
23     scanf("%I64d%I64d\n",&m,&d);
24     memset(ans,-1,sizeof(ans));
25     scanf("%c",&c);
26     while(c!='\n')
27     {
28         w[++len1]=c-'0';
29         scanf("%c",&c);
30     }
31     w[len1]--;
32     for(i=len1;i>=1;i--)
33     {
34         if(w[i]>=0)    break;
35         w[i-1]--;
36         w[i]+=10;
37     }
38     ans1=dp(1,0,true,true);
39     memset(w,0,sizeof(w));
40     len1=0;
41     scanf("%c",&c);
42     while(c!='\n')
43     {
44         w[++len1]=c-'0';
45         scanf("%c",&c);
46     }
47     ans2=dp(1,0,true,true);
48     printf("%I64d",(ans2-ans1+md)%md);
49     return 0;
50 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:for循环语句中的先后执行顺序

下一篇:快速双边滤波 附完整C代码