Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

09/11
13:15
一般动规与递推

[bzoj 4421] [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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

4

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

(i,j)%m=0的充要条件是(1,i)%m=0且(1,j)%m=0,所以只要统计有多少个x满足(1,x)%m=0就好了,答案就是2^(x-1),需要特判无解的情况

c++:

pascal:

 

[bzoj 4421] [Cerc2015] Digit Division