当前位置：网站首页>CodeForces - 628D (digital dp)

CodeForces - 628D (digital dp)

2022-08-10 12:16: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

题目大意：

Find the number of a certain number in an interval,需要是m的倍数,And odd digits cannot be includedd,Even numbers are requiredd.The number of digits is2000位.

思路：

首先是数位dp.

关于m的限制,Just calculate the edge modulo directly.d限制,Need to discuss parity.

The number of digits is large,Strings are required,这样的话,闭区间,The number on the left minus one is not easy to calculate,需要特判一下.

代码：

       
       #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://yzsam.com/2022/222/202208101129429764.html

当前位置：网站首页>CodeForces - 628D (digital dp)

CodeForces - 628D (digital dp)

边栏推荐

猜你喜欢

随机推荐