Magic Numbers CodeForces - 628D
2018-06-17 21:49:46来源:未知 阅读 ()
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代码
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
- CodeForces 1313D Happy New Year 2020-03-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash