当前位置：网站首页>CodeForces - 628D （数位dp）

CodeForces - 628D （数位dp）

2022-08-10 11:32:00 【51CTO】

Consider the decimal presentation of an integer. Let's call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.

For example, the numbers 1727374, 17, 1 are 7-magic but 77, 7, 123, 34, 71 are not 7-magic. On the other hand the number 7 is 0-magic, 123 is 2-magic, 34 is 4-magicand 71 is 1-magic.

Find the number of d-magic numbers in the segment [a, b] that are multiple of m. Because the answer can be very huge you should only find its value modulo 109 + 7 (so you should find the remainder after dividing by 109 + 7).

Input

The first line contains two integers m, d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — the parameters from the problem statement.

The second line contains positive integer a in decimal presentation (without leading zeroes).

The third line contains positive integer b in decimal presentation (without leading zeroes).

It is guaranteed that a ≤ b, the number of digits in a and b are the same and don't exceed 2000.

Output

Print the only integer a — the remainder after dividing by 109 + 7 of the number of d-magic numbers in segment [a, b] that are multiple of m.

Examples

Input

2 6 10 99

Output

Input

2 0 1 9

Output

Input

19 7 1000 9999

Output

题目大意：

求一个区间内某种数的个数，需要是m的倍数，并且奇数位不能包含d，偶数为必须包含d。数的位数是2000位。

思路：

首先是数位dp。

关于m的限制，直接便计算边取模就行。d限制，需要分奇偶讨论一下。

数的位数很大，需要用字符串，这样的话，闭区间，左边的数减一不好计算，需要特判一下。

代码：

       
       #include <cstdio>
       
       #include <iostream>
       
       #include <cstring>
       
       #include <vector>
       
       #include <cmath>
       
       #include <algorithm>
       
       #include <map>
       
       #include <queue>
       
       #include <cmath>
       
       #include <ctime>
       
       using 
       
       namespace 
       
       std;
       
       #define ll long long
       
       const 
       
       int 
       
       mod
       
       =
       
       1e9
       
       +
       
       7;
       
       long 
       
       long 
       
       a[
       
       2200];
       
       long 
       
       long 
       
       dp[
       
       2200][
       
       2100][
       
       2];
       
       int 
       
       m, 
       
       id;
       
       int 
       
       l;
       
       long 
       
       long 
       
       dfs(
       
       int 
       
       pos, 
       
       int 
       
       sum, 
       
       int 
       
       jo,
       
       int 
       
       limit)
       
{
       
       if (
       
       pos 
       
       == 
       
       -
       
       1)
       
    {
       
       return 
       
       !
       
       sum
       
       &&
       
       jo;
       
    }
       
       if (
       
       !
       
       limit
       
       &&
       
       dp[
       
       pos][
       
       sum][
       
       jo] 
       
       != 
       
       -
       
       1)
       
       return 
       
       dp[
       
       pos][
       
       sum][
       
       jo];
       
       long 
       
       long 
       
       sun 
       
       = 
       
       0;
       
       int 
       
       end 
       
       = 
       
       limit 
       
       ? 
       
       a[
       
       pos] : 
       
       9;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0;
       
       i 
       
       <= 
       
       end;
       
       i
       
       ++)
       
    {
       
       if ((
       
       l
       
       -
       
       pos)
       
       %
       
       2
       
       ==
       
       0)
       
        {
       
       sun 
       
       = (
       
       sun
       
       +
       
       dfs(
       
       pos 
       
       - 
       
       1, (
       
       sum
       
       *
       
       10 
       
       + 
       
       i) 
       
       % 
       
       m,
       
       jo
       
       &&(
       
       i
       
       ==
       
       id), 
       
       limit
       
       &&
       
       i 
       
       == 
       
       a[
       
       pos]))
       
       %
       
       mod;
       
        }
       
       else
       
        {
       
       sun 
       
       = (
       
       sun
       
       +
       
       dfs(
       
       pos 
       
       - 
       
       1, (
       
       sum
       
       *
       
       10 
       
       + 
       
       i) 
       
       % 
       
       m, (
       
       jo
       
       &&!(
       
       i
       
       ==
       
       id)),
       
       limit
       
       &&
       
       i 
       
       == 
       
       a[
       
       pos]))
       
       %
       
       mod;
       
        }
       
    }
       
       if (
       
       !
       
       limit)
       
       dp[
       
       pos][
       
       sum][
       
       jo] 
       
       = 
       
       sun;
       
       return 
       
       sun;
       
}
       
       long  
       
       long 
       
       go(
       
       char 
       
       x[])
       
{
       
       int 
       
       pos 
       
       = 
       
       strlen(
       
       x);
       
       l
       
       =
       
       pos;
       
       memset(
       
       a,
       
       0,
       
       sizeof(
       
       a));
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       pos;
       
       i
       
       ++)
       
    {
       
       a[
       
       pos
       
       -
       
       i
       
       -
       
       1]
       
       =
       
       x[
       
       i]
       
       -
       
       '0';
       
    }
       
       return 
       
       dfs(
       
       pos 
       
       - 
       
       1, 
       
       0, 
       
       1,
       
       1);
       
}
       
       char 
       
       b[
       
       2200],
       
       c[
       
       2200];
       
       int 
       
       pan(
       
       char 
       
       x[])
       
{
       
       int 
       
       pos 
       
       = 
       
       strlen(
       
       x);
       
       int 
       
       sum
       
       =
       
       0;
       
       int 
       
       flag
       
       =
       
       0;
       
       int 
       
       flag1
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       pos;
       
       i
       
       ++)
       
    {
       
       int 
       
       v
       
       =
       
       x[
       
       i]
       
       -
       
       '0';
       
       sum
       
       =(
       
       sum
       
       *
       
       10
       
       +
       
       v)
       
       %
       
       m;
       
       if(
       
       i
       
       %
       
       2
       
       ==
       
       1)
       
        {
       
       if(
       
       v
       
       !=
       
       id)
       
            {
       
       flag
       
       =
       
       1;
       
       break;
       
            }
       
        }
       
       else
       
        {
       
       if(
       
       v
       
       ==
       
       id)
       
            {
       
       flag1
       
       =
       
       1;
       
       break;
       
            }
       
        }
       
    }
       
       if(
       
       !
       
       sum
       
       &&!
       
       flag
       
       &&!
       
       flag1)
       
       return 
       
       1;
       
       else 
       
       return 
       
       0;
       
}
       
       int 
       
       main()
       
{
       
       scanf(
       
       "%d%d", 
       
       &
       
       m, 
       
       &
       
       id);
       
       scanf(
       
       "%s%s", 
       
       b, 
       
       c);
       
       memset(
       
       dp, 
       
       -
       
       1, 
       
       sizeof(
       
       dp));
       
       printf(
       
       "%lld\n", (
       
       go(
       
       c)
       
       -
       
       go(
       
       b)
       
       +
       
       pan(
       
       b)
       
       +
       
       mod)
       
       %
       
       mod);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15747246/5563002

当前位置：网站首页>CodeForces - 628D （数位dp）

CodeForces - 628D （数位dp）

边栏推荐

猜你喜欢

随机推荐