【BZOJ4421】[Cerc2015] Digit Division 动态规划
2024-08-28 08:19:44
【BZOJ4421】[Cerc2015] Digit Division
Description
给出一个数字串,现将其分成一个或多个子串,要求分出来的每个子串能Mod M等于0.
将方案数(mod 10^9+7)
Input
给出N,M,其中1<=N<=300 000,1<=M<=1000 000.
接下来一行,一个数字串,长度为N。
Output
如题
Sample Input
4 2
1246
1246
Sample Output
4
题解:如果一个前缀a%m==0,另一个长一点的前缀b%m==0,那么他们的中间部分(b-a*10^i)%m一定也是0,那就相当于我们每搜到一个前缀为0的位置就可以把这个串从这里切开,那么如果原串有n个前缀%m==0,显然除了最后一个必须切以外,每个前缀我们可以选择切或不切,答案就是2^n
不要比谁的代码长度短了!!!
#include <cstdio>
int n,m,sum,ans,j;
char str[300010];
int main()
{
scanf("%d%d%s",&n,&m,str),ans=1;
while(str[j]) sum=(sum*10+str[j]-'0')%m,ans=(!sum&&str[j+1])?(ans*2%1000000007):ans,j++;
printf("%d",(!sum)?ans:0);
return 0;
}
最新文章
- freeswitch 使用mysql替换默认的sqlite
- StartUML反向(逆向)Java工程通过代码生成类图
- JavaScript-table+大图滚动
- iOS的TCP/IP协议族剖析&;&;Socket
- jquery 打印宽高
- winform界面闪退
- logstash 因为jdk版本不对造成索引时间戳失败
- 【摘抄】Application.StartupPath和System.Environment.CurrentDirectory的区别
- offsetWidth、offsetleft 等图文详解
- 【转】Android通过Wifi来调试你的应用
- Appium测试时如何关联到Genymotion模拟器
- 在 JPA、Hibernate 和 Spring 中配置 Ehcache 缓存
- 机器学习——kNN(1)基本原理
- 低延时的P2P HLS直播技术实践
- 填坑:Windows下使用OpenSSL生成自签证书(很简单,一个晚上搞明白的,让后来者少走弯路)
- Linux CFS调度器之虚拟时钟vruntime与调度延迟--Linux进程的管理与调度(二十六)
- [No0000174]Spring常用注解(收藏大全)
- HTML <;frame>; 标签的 src 属性
- shell中$#等含义
- 图像中的artifacts
热门文章
- IT精英们不断上演的十大傻事(组图)
- 安装应用程序 报“ 997 重叠 I/O 操作在进行中”错解决办法
- intellij jetBrains phpstorm/webstorm/IDEA 编辑器使用诀窍
- 使用forever运行nodejs应用
- js setInterval()函数 [倒计时用]
- python学习之items()
- InnoDB:文件
- pair + map 函数结合使用
- SQL练习题汇总(Sqlserver和Mysql版本)
- tp框架事务处理