BZOJ 4421: [Cerc2015] Digit Division

2023-07-18 14:47:16

4421: [Cerc2015] Digit Division

Time Limit: 1 Sec Memory Limit: 512 MB
Submit: 348 Solved: 202
[Submit][Status][Discuss]

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

HINT

Source

[Submit][Status][Discuss]

只需要求出所有能使得前缀数字串在mod意义下等于0的位置,设为$t$，则从这些位置任意切开，得到的串均满足要求。每个位置有两种选项（切或不切）答案是$2^{t}$。

 #include <cstdio>

 const int mod = 1e9 + ;

 int n, m, t;

 char s[];

 inline int pow(long long a, int b)

 {

     long long r = ;

     while (b)

     {

         if (b & )

         {

             r *= a;

             if (r >= mod)

                 r %= mod;

         }

         b >>= ;

         a = a * a;

         if (a >= mod)

             a %= mod;

     }

     return r;

 }

 signed main(void)

 {

     scanf("%d%d%s", &n, &m, s);

     int sum = ;

     for (char *c = s; *c; ++c)

     {

         sum = sum *  + *c - '';

         if (sum >= m)

             sum %= m;

         if (sum == )

             ++t;

     }

     printf("%d\n", sum ?  : pow(, t - ));

 }

@Author: YouSiki

码农公寓