problem If you write a positive integer in decimal notation (without leading 0) and look…
- User
problem
If you write a positive integer in decimal notation (without leading 0) and look at the digit numbers in order, when the number increases and decreases alternately, the number is "zigza". Let's call it. For example, 2947 is a zigzag number because the digit numbers are in the order of 2 → 9 → 4 → 7 and increase → decrease → increase. In addition, 71946 is a zigzag number because it is in the order of decrease → increase → decrease → increase. On the other hand, 123, 71446, 71442 and 88 are not zigzag numbers. A one-digit positive integer is considered to be a zigzag number.
Create a program that finds the remainder of the number of zigzags divided by 10000 out of multiples of M between A and B. input
The input consists of three lines, with one positive integer written on each line.
The integer on the first line represents A, the integer on the second line represents B, and the integer on the third line represents M. These satisfy 1 ≤ A ≤ B ≤ 10500 and 1 ≤ M ≤ 500.
- Note that the values of A and B may not fit in the data types that represent ordinary integers.
output
Output the remainder of the number of zigzag numbers divided by 10000 out of multiples of M between A and B in one line.
Input / output example
Input example 1
100 200 Five
Output example 1
13
In I / O example 1, the number of zigzags that are multiples of 5 from 100 to 200 is 13 of 105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195. ..
Input example 2
6 1234567 3
Output example 2
246
In I / O example 2, there are 50246 zigzag numbers that are multiples of 3 from 6 to 1234567, so 246, which is the remainder of dividing it by 10000, is output.
The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.
Example
Input
100 200 5
Output
13
Assistant
We need to solve: Count numbers between A and B inclusive that are multiples of M and are "zigzag" numbers, then output count mod 10000.
Constraints: A,B up to 10^500 (so huge, length up to 500 digits). M <= 500. Need to count numbers with modular constraints and zigzag property.
We need to compute number of numbers x in [A,B] such that x % M == 0 and x is zigzag. Zigzag means when reading digits from left to right, each adjacent triple? Actually definition: For a number written in decimal without leading zeros, consider the sequence of digits d1 d2 ... dk. The number is zigzag if the pattern of increases and decreases alternates: i.e., for i from 2 to k-1, we have (d_i - d_{i-1}) * (d_{i+1} - d_i) < 0? Actually they said: "when the number increases and decreases alternately". For example 2947: 2<9 (increase), 9>4 (decrease), 4<7 (increase). So the pattern of comparisons between successive digits should alternate: increase, decrease, increase, ... OR decrease, increase, decrease, ... Also they said a one-digit positive integer is considered zigzag. Two-digit numbers? For two-digit, there is only one comparison. According to definition: "when the number increases and decreases alternately, the number is zigzag." For two-digit, we have only one change; is that considered alternating? Let's check: They gave examples: 2947 (4-digit), 71946 (5-digit). Also they gave non-examples: 123 (strictly increasing, but that's not alternating because all increases, no decrease), 71446 (digits: 7>1 decrease, 1<4 increase, 4=4? Actually 4=4 is equal, not increase or decrease. They said 71446 is not a zigzag number. The condition likely requires strict inequalities, i.e., each adjacent comparison must be either increase (d_i < d_{i+1}) or decrease (d_i > d_{i+1}), and they must alternate. So for two-digit numbers: If digits are equal, not allowed. If they are different, then there is a single comparison, but does that count as alternating? Since there's only one transition, there is no violation of alternation. The definition: "when the number increases and decreases alternately" could be interpreted as the pattern of increases and decreases must alternate, meaning that if there are at least two comparisons, they must alternate. For a two-digit number, there's only one comparison, so it's trivially alternating? Let's see if they consider two-digit numbers as zigzag. In example 2, they count from 6 to 1234567. They output 246 (mod 10000). Let's think: Possibly they include two-digit numbers? We can't be sure. But we can infer from common definitions: Usually "zigzag" or "alternating" numbers require at least two digits to have a pattern; but they said "A one-digit positive integer is considered to be a zigzag number." They didn't explicitly state two-digit. However, the typical problem "Zigzag numbers" often includes numbers of any length where consecutive digits alternately increase and decrease (and often two-digit numbers are considered zigzag as long as digits are not equal). But I'd double-check: In the example I/O, for range 100 to 200 (3-digit numbers only) they counted 13 numbers: 105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195. Let's see if any two-digit numbers are in that range? No, because A=100, B=200, it's all three-digit numbers. So that doesn't inform.
We can try to deduce from problem statements from JOI (Japan Committee for Information Olympics). There might be known problem "Zig-Zag numbers" from JOI? Possibly from JOI 2009/2010? I'm not sure. But we can also reason: For two-digit numbers, if digits are equal, it's not zigzag because it's not increasing nor decreasing? Usually equality breaks alternation. If digits are different, there is exactly one comparison, but there is no opportunity to "alternate". Many problems consider numbers of length 2 as zigzag because you cannot violate alternation. Let's check typical definitions: "A number is called zigzag if its digits alternately increase and decrease." That definition often includes numbers with length 1 and length 2 as trivially satisfying the condition, as long as the digits are not equal for length 2? Actually if length 2, it's just one increase or decrease; there is no alternation but it's considered okay because there is no pair of successive changes to break the alternation. Some problems explicitly say "For numbers with at least two digits, the digits must alternately increase and decrease", implying that two-digit numbers are included. However, they gave non-example: 71446. Here digits: 7>1 (decrease), 1<4 (increase), 4=4 (equal) - that's not increase or decrease; so it fails because equality not allowed. They also gave 71442: 7>1 decrease, 1<4 increase, 4>4? Actually 4 and 4 equal? Wait 71442: digits: 7,1,4,4,2. Compare 7>1 decrease; 1<4 increase; 4=4 equal (not allowed); 4>2 decrease but the pattern might be broken anyway. So equality is not allowed. Also 88: two-digit equal digits, not allowed. So 88 is not zigzag. So for two-digit numbers, if digits are not equal, they would be zigzag? Possibly yes. But let's confirm: If we take 12: 1<2 increase; does it count as zigzag? Probably yes. There's no example to contradict.
Thus we assume: A positive integer is zigzag if either its length is 1, OR for length >=2, for every adjacent pair (i,i+1), we have d_i != d_{i+1} and the sign of (d_{i+1} - d_i) alternates, i.e., for i=1..k-2, (d_{i+1} - d_i)(d_{i+2} - d_{i+1}) < 0. For two-digit, there is no such condition, only that d1 != d2? Actually they said 88 is not zigzag. So d1 != d2 required? Possibly yes: because if digits equal, it's neither increase nor decrease. So two-digit numbers with equal digits are not zigzag. So condition for any length >=2: all consecutive digits must be strictly increasing or decreasing (i.e., no equal), and the sequence of comparisons must alternate. For two-digit, the condition reduces to d1 != d2 (since alternation condition is vacuously true). For three-digit, we require d1 != d2, d2 != d3, and (d2-d1)(d3-d2) < 0.
We'll adopt that.
Now we need to count numbers in range [A, B] with given modulus condition. A and B are up to 500 digits, M <=500. Classic digit DP for two bounds with huge numbers, but we need to handle large A,B as strings.
We can compute f(N) = count of numbers <= N that are multiples of M and zigzag. Then answer = f(B) - f(A-1) (with careful when A=1, but we can handle). Since A and B can be huge, we need to compute A-1 by subtracting 1 from the decimal string.
Now count numbers up to N (string) with modulus condition and zigzag property. This is a digit DP with states: position (index from 0 to len), whether already less than N (tight flag), the previous digit (if any), the trend (whether we are expecting increase or decrease next, or undefined for start), and the current remainder mod M. Also need to handle leading zeros because numbers have no leading zeros except the number 0? But numbers are positive, and we are counting from 1 up to N. However, A,B are positive integers, so we count only positive numbers. In digit DP, we typically consider numbers with leading zeros as representations of numbers with fewer digits. But careful: The zigzag condition is defined for the decimal representation without leading zeros. So we need to ensure that we don't count numbers with leading zeros (except the number 0, but we don't count 0 as it's not positive). So we can treat the DP as generating numbers of exactly len digits (where len = length of N), but allowing leading zeros to represent numbers with fewer digits, but then we must enforce that the first non-zero digit is the start and that we don't count the all-zero number. Additionally, zigzag condition for numbers with leading zeros would be weird. So we need to incorporate a flag "started" indicating whether we have placed a non-zero digit yet. When not started, we skip zeros and don't consider any zigzag conditions. Once we start, we record the first digit, and then enforce conditions for subsequent digits.
However, careful: For numbers with varying lengths, the zigzag condition applies to the actual digits (without leading zeros). So if we have a number with length L (< len), the first digit is non-zero and all conditions apply from the first digit onward. That's okay if we start DP with started flag false, and when we place first non-zero digit, we treat it as first digit with no previous digit, so no comparison needed. Then after placing the second digit (first after start), we have a direction (increase or decrease relative to first digit). Then we need to enforce alternation.
But note: For single-digit numbers (L=1), they are always zigzag, regardless of digit (non-zero, since positive integer). So in DP, if we start a number and then end after placing only one digit (i.e., we reach end of string without placing more digits), that number is counted. But also numbers with more digits must satisfy conditions.
Also numbers with two digits: after placing first digit (started), then we place second digit; we must ensure that second digit != first digit (strict inequality). There's no alternation check because there is only one comparison. So condition: if we have exactly two digits, it's okay if d1 != d2. But note: Is there any additional requirement? For example, for three digits: after first and second, we have direction; then third digit must be opposite direction relative to second, and also not equal to second.
Thus DP state must capture:
- pos: current index (0..len)
- tight: boolean if prefix equals N's prefix so far.
- started: boolean if we have placed any non-zero digit yet.
- prev_digit: the last placed digit (0-9) if started and we have at least one digit placed. Actually when started, we have the current last digit. For the condition when placing next digit, we need to know the previous digit and the previous direction? Actually we need to enforce alternation. To decide if we can place a digit d at current position, we need to know the trend direction from the previous step? Actually the condition is: For each new digit we add, if the number of digits placed so far (since start) is >=2, then we need to check the sign of (new_digit - prev_digit) relative to the previous sign. So we need to know the direction of the last comparison (increase or decrease). Also we need to know prev_digit.
But we could also deduce direction from the last two digits? But if we store prev_digit and prev_dir (increase/decrease) after the last comparison. However, when we have placed exactly one digit (started, but only one digit so far), there is no direction yet. So we need to store a state indicating the status of the sequence: either:
- state = 0: not started (no digits placed)
- state = 1: only one digit placed (so we have prev_digit but no direction)
- state = 2: at least two digits placed, and we know the last direction (whether the last comparison was increase or decrease). Actually to enforce alternation, we need to know the direction of the last comparison so that the next comparison must be opposite.
But we could also store prev_digit and the last direction or a flag indicating what the next expected direction? Since after placing at least two digits, the pattern alternates. So if we have placed k digits (k>=2), then the last comparison (between digit k-1 and digit k) has a direction (up=1 for increase, down=0 for decrease perhaps). Then the next comparison must be opposite.
Thus DP state could be: (pos, tight, started, prev_digit, last_dir) with last_dir = -1 for no direction (i.e., only one digit placed), or 0 for decrease, 1 for increase. But we also need to ensure that we never have equal digits; that is enforced during transition: if placed digit d, and started and we have prev_digit, we must have d != prev_digit. Then compute the new direction: if prev_digit < d -> direction = 1 (increase); else direction = 0 (decrease). Then if we had a last_dir (i.e., from state with last_dir != -1), we must have new direction != last_dir (i.e., opposite). If last_dir = -1 (only one digit before), then we accept any direction and set last_dir to new direction.
Also, we have to consider numbers that end with only one digit (state with started and only one digit placed) as valid, as well as numbers that end with more digits as long as conditions held throughout.
Now, we also have modulo M condition. So we maintain remainder mod M.
Thus DP dimension: pos up to 500, tight 2, started 2, prev_digit 10 (but only relevant if started), last_dir maybe 3 values (-1, 0, 1). But prev_digit is only needed when started. When started false, we don't have prev_digit. So we can combine started and prev_digit: use prev_digit = 10 to indicate not started or not applicable. However last_dir only meaningful when started and have at least 2 digits.
But we need to be careful: When started is false, we haven't placed any digit, so prev_digit is irrelevant, last_dir irrelevant. When we place first non-zero digit, we set started=true, prev_digit = that digit, last_dir = -1. Then we proceed.
But note: The number could have leading zeros after start? Actually once started, we can't place leading zeros; zeros are allowed as digits within the number (like 101? But zero is a digit; we must consider that digits can be 0 after the first digit. For example, 101: digits 1,0,1. Check zigzag: 1>0 decrease, 0<1 increase -> alternates, and digits not equal. So zeros are allowed after first digit. So after started, we allow digits 0-9.
But we must ensure that we don't count numbers with leading zeros before start. That's fine.
Now DP for counting numbers <= N. Typical digit DP: iterate over digits, maintain states.
Complexities: len <= 500, M <= 500, states: pos (500) * tight (2) * started (2) * prev_digit (10 maybe 11) * last_dir (3) * mod (500). That's 500 * 2 * 2 * 11 * 3 * 500 = 500 * 2 * 2 = 2000; 2000 * 11 = 22000; 22000 * 3 = 66000; 66000 * 500 = 33,000,000. That's 33 million states. That might be high but possibly okay in C++ if using DP with memoization and only reachable states? However 500 length and each state transition loops over digit (0-9) leading to maybe 330M operations, might be borderline but could be optimized with table DP and iterative? But 33 million states times 10 digits = 330 million, which is doable in C++ with careful optimization? However Python might be too slow. But we can try to reduce states.
We can compress prev_digit to 10 values (0-9). But note that when started is false, prev_digit is irrelevant; we can treat as 0 but not used. Actually we could store prev_digit only when started true, but we can incorporate started flag into prev_digit: e.g., prev_digit = 10 for not started. Then last_dir: we need to store only when started and have at least two digits? But we can also store last_dir = -1 for not started or only one digit? Let's define:
- prev_digit: -1 for not started; else 0-9 for last digit placed.
- last_dir: -1 for "no direction yet" (i.e., either not started or exactly one digit placed); else 0 for last was decrease, 1 for last was increase. But careful: if not started, we don't need to consider direction. However we can treat as -1. When we start with first digit, we set prev_digit to that digit, and last_dir remains -1. When we add second digit, we compute new_dir, and if last_dir == -1, it's allowed, then we set last_dir = new_dir. When adding third digit, we must have new_dir != last_dir.
Thus DP state: (pos, tight, prev_digit (0-9 or -1), last_dir (-1,0,1), rem). That's pos up to 500, tight 2, prev_digit 11 values (-1..9, total 11), last_dir 3, rem 500. That's 5002113500 = same 33 million. Might be okay in Python with memoization recursion? Possibly too heavy.
We can attempt to reduce dimension by noticing that M is at most 500, and length up to 500, so DP size could be large but maybe we can use iterative DP with rolling arrays for pos dimension, reducing memory. Also we can compress prev_digit to 10 (since when prev_digit = -1, it's effectively started false). But we can treat prev_digit as 10 with value 10 for not started, but that's 11.
But 33 million states, each storing integer counts mod 10000. That's memory ~ 33M * 2 bytes? Actually Python integers are heavy, so we can't store that many states. We need to optimize.
We can try to use DP that processes digit by digit and uses a dictionary for states (since many states may be unreachable). However the modulus remainder and prev_digit can take many combos, but maybe many are unreachable due to tight? Actually for each pos, there could be many combos of (tight, prev, dir, rem). But in a typical digit DP for counting numbers with constraints, we use memoization over (pos, tight, started, prev_digit?, last_dir?, rem) and it works for lengths up to 20-30. For length 500, it's too many states because the remainder can be 0..M-1 and M up to 500, that's 500 possibilities. The number of prev_digit (11) and last_dir (3) is small. But the pos dimension is 500. However, in recursion, the number of distinct states visited might be len * tight * started * prev * dir * rem, which is at most 50022103*500? That's 30 million. But with memoization, we would store that many entries, each a Python dict entry overhead high, not feasible.
We need to use iterative DP that processes digit by digit and uses arrays of size [2][2][11][3][500] for current pos and next pos. But that's still 22113500 = 22=4, 411=44, 443=132, 132500=66,000. Wait: 2 (tight?) Actually tight is a flag, but for iterative DP we normally have two categories: for each position we have states for whether the prefix is already less than N (tight=0) or still equal (tight=1). However we often use DP[pos][tight][...] but we can compress by using two arrays: dp for current tight=0 and dp for tight=1? Actually we need to handle both tight states simultaneously. But we can treat dp as a dictionary keyed by (tight, prev, dir, rem). However we can use two separate arrays: one for tight=0 (already smaller) and one for tight=1 (still equal). But note that for tight=0, the digit choices are unrestricted (0-9). For tight=1, choices limited to digits <= N[pos].
When iterating, we can update accordingly. So we can have dp[tight][prev][dir][rem] where prev index maybe 0..10 (with 10 representing not started). dir index 0,1,2 mapping: -1->0? Actually we can map -1 to 0, increase (1) to 1, decrease (0) to 2? Let's define: Let dir = 0 meaning "none" (no direction yet, i.e., started but only one digit or not started? But not started should have prev=10, dir irrelevant? We can combine them.) But we can simplify: Instead of having separate started flag, we can treat prev=10 as not started. And dir can be 0 meaning none (when prev=10, dir=0) or when prev!=10 but only one digit, dir=0. And when prev!=10 and at least two digits, dir=1 (increase) or 2 (decrease). But we must differentiate between increase and decrease for next direction.
So define:
- prev: 0..9 if we have started and have placed at least one digit; else 10 for not started.
- dir: 0 -> no direction (either not started or only one digit placed), 1 -> last comparison was increase, 2 -> last comparison was decrease.
However when prev=10, we must enforce that dir is 0 (or we can just set dir=0 and ignore). For states with prev!=10, dir can be 0,1,2. But careful: If we have prev!=10 and we are in state with dir=0, that means only one digit placed so far. If we have dir=1 or 2, that means at least two digits placed and the last comparison direction as indicated.
Thus we can have dp[tight][prev][dir][rem] counts. Dimensions: tight=0/1, prev=11 (0-9 plus 10), dir=3 (0,1,2), rem=M (0..M-1). That's 2113M = 66M <= 66*500 = 33,000. That's only 33k states per position! That's manageable. Because we removed the pos dimension by iterating position by position and updating a DP table for the current prefix. Actually we need to process each digit, and for each position we have a DP representing counts for numbers formed from the first pos digits (prefix). After processing all digits, we sum appropriate states.
So iterative DP over the digits of N works: Initialize dp for position 0 (before any digit) with one state: tight=1 (since no digits yet, it's equal to prefix of N? Actually for typical digit DP we start with tight=1 and the rest empty. But we need to handle leading zeros. So start with dp[tight=1][prev=10][dir=0][rem=0] = 1. This represents the empty prefix (no digits placed yet, and we haven't started the number). Then for each position i from 0 to len-1 (each digit of N), we compute a new DP table next_dp initialized to zeros. For each state (tight, prev, dir, rem) with count c, we determine the allowed digit range: if tight=1, digits from 0 to digit_N[i]; else 0..9. For each digit d in that range, we compute new_tight = tight && (d == digit_N[i]). Then we need to incorporate the zigzag condition and started logic.
Transition logic:
-
If prev == 10 (not started): that means we haven't placed any non-zero digit yet. If d == 0, we remain not started? But careful: we are building numbers of exactly len digits with leading zeros allowed. But we only consider numbers that are positive. However if we keep d=0 and remain not started, that means we are still at leading zeros. That's allowed as long as we haven't finished yet. At the end, we must ensure that the number is started (i.e., have at least one non-zero digit) to be counted, because we count positive integers only. So at the final stage, we only sum states where started is true (prev != 10). For transition: If d == 0 and prev==10: new_prev = 10 (still not started), new_dir = 0, new_rem = (rem10 + d) % M. However note that if d=0 and we are not started, we are effectively still having leading zeros. But the remainder calculation: the number's value is formed by digits; leading zeros don't affect value. When we are not started, the actual number hasn't begun, but the remainder of the prefix (including leading zeros) is computed as if zeros are part of the number (but they are, but leading zeros don't affect numeric value). For example, number 012 is 12. The numeric value is formed by digits as usual. When we treat the DP, we compute remainder as we append digits, regardless of started. So rem update: new_rem = (rem * 10 + d) % M, even if d=0 and not started. That's correct because the final number's value will be the same as the digit sequence interpreted as a number, including leading zeros. Since we later only consider numbers that have started (non-zero first digit), but the numeric value includes zeros before start? Actually if we have leading zeros, the number's numeric value is less than 10^(len-1). But the digits we process include leading zeros to make length exactly len. However the number represented by that digit sequence (with leading zeros) is exactly the integer we intend, because leading zeros don't change value. So it's fine to compute remainder along the way, including leading zeros, because (rem10+d) works. For example, if we eventually have digits "0012", the numeric value is 12, and the remainder computed from the string "0012" is same as from "12". Since we start with rem=0, after processing '0' -> (0*10+0)%M=0, after next '0' ->0, after '1'->1, after '2'->12. So works.
-
If prev == 10 (not started) and d != 0: then we start the number. We set new_prev = d (the first digit). Since we only have one digit, new_dir = 0 (no direction yet). new_rem = (rem*10 + d) % M.
-
If prev != 10 (started already): we already have at least one digit placed. Now we need to enforce that d != prev (cannot equal), because consecutive digits must be strictly different. If d == prev, skip this transition (invalid). Next, compute comp = (d > prev) ? 1 : (d < prev) ? 2? Actually we defined dir: 1 for increase, 2 for decrease. So if d > prev, direction = 1 (increase); if d < prev, direction = 2 (decrease). Now check the alternation condition: if current dir (from state) is 0, meaning we have only one digit so far (i.e., no previous direction), then this new direction is always acceptable. Set new_dir = direction. If current dir is non-zero (1 or 2), then we require that direction != current dir (i.e., opposite). If it's equal, then that would be two consecutive same directions (e.g., increase then increase) and it's invalid. So if direction == current dir, skip. Else (direction != current dir) then new_dir = direction.
After these checks, new_prev = d, new_rem = (rem*10 + d) % M.
Additionally, if the number has started, we also consider that we might end after this position (i.e., the number may have fewer digits than len). But since we are processing fixed length len (the length of N), and we allow leading zeros, the number ends exactly at the final digit. So we cannot end early; we are forced to produce exactly len digits. But that includes numbers with leading zeros, i.e., numbers with fewer digits will be represented with leading zeros. That's fine. However, at the end, we must only count those numbers that have started (i.e., at least one non-zero digit). Also note: numbers like "0" (all zeros) would be excluded. Also numbers with all zeros but started false are zero, which is not positive.
One nuance: The digit DP approach with leading zeros counts numbers from 0 to N inclusive, with length exactly len (by padding with leading zeros). Then we count numbers >0 that satisfy condition. However, we must be careful about the upper bound N: For numbers with fewer digits than len, they are represented with leading zeros, and they are all less than N as long as N has len digits (since leading zeros produce numbers with less digits, which are less than any number with len digits that starts with a non-zero digit). But is it guaranteed that any number with fewer digits is <= N? Yes, because N has exactly len digits and its first digit is non-zero (since N is a positive integer without leading zeros). Any number with fewer than len digits is less than 10^{len-1} which is <= N? Actually if N is exactly 10^{len-1} (like 1000...0), then numbers with fewer digits are < N, so they are included. If N is smaller than that? But N has len digits, so its value is at least 10^{len-1}. So numbers with fewer digits (i.e., length < len) are in range [0, 10^{len-1}-1] which is strictly less than 10^{len-1} <= N. So they are all < N, so they are included when counting numbers <= N. However, if we use a DP that considers numbers with exactly len digits (including leading zeros), we need to ensure that we count numbers with length exactly len (i.e., with first digit non-zero) and also numbers with shorter length (leading zeros). The DP with leading zeros automatically counts both, because leading zeros are allowed. For numbers with shorter length, the representation will have leading zeros, and the DP will treat them as numbers with first digit zero (started false until a non-zero appears). At the end, we require started true to count. So it correctly counts numbers from 1 to N inclusive.
Edge case: N=0? Not in input as A,B >=1. So fine.
Thus we can implement a DP function count_zigzag_mod(N_str, M) that returns count of numbers from 1 to N inclusive that are multiples of M and zigzag.
Implementation details:
- Convert N_str to list of digits (int) from most significant to least. Let L = len(N_str).
- Initialize dp array: we can use a 4D array? But we have dimensions: tight (2), prev (11), dir (3), rem (M). Use dictionary for sparsity? However M up to 500 and prev up to 11, dir 3, tight 2, total size 2113*500=33k, which is small. So we can use a 4D list (or nested loops) to store integers (mod 10000). Since we need to compute counts modulo 10000, we can store modulo 10000.
We'll represent dp as a list of size [2][11][3][M] of ints, initialized to 0. But we need to iterate over all states each digit. That is 33k per position, times L up to 500 => 16.5 million state updates, each with inner loop over digits 0-9 (10). That's 165 million operations, maybe okay in Python if optimized with loops? Might be borderline but possibly okay with PyPy or using numpy? 165 million simple integer ops in Python could be slow (maybe ~2 seconds per 100 million? Possibly ~5 seconds). But we can optimize by precomputing transitions for each (prev, dir, d) to (new_prev, new_dir, valid) and also using for loops only over allowed digits per state and tight conditions. However we have to handle tight=1 where digits limited to N[i]. But still we need to loop over all states and over digits.
We could also compress prev and dir into a combined state for started? But 33k * 500 = 16.5M, which is not too high; 16.5M state updates, each with up to 10 digits: 165M transitions. But perhaps we can reduce digits loop for tight=0 states: For tight=0, digit range is 0..9, which is 10. For tight=1, digits up to N[i] maybe less. However we can still precompute for each (prev, dir) the possible outcomes for each digit d, like new_prev, new_dir, and whether allowed.
But the major cost is nested loops: for each pos, for each tight, for each prev, for each dir, for each rem, we iterate digits. That's 500 * 2 * 11 * 3 * M * (average digits). With M=500, that's 5002113500 = 16.5M states per pos? Wait, that's not right: The number of states is (2 * 11 * 3 * M) = ~33,000. For each pos, we iterate over all states (33k) and for each state we iterate over digits (0..9). That's ~330k operations per position, times 500 = 165 million. So it's 165 million digit transitions, not 16.5 million states times 10 = 165 million. That's okay.
165 million in Python might be borderline but possible with PyPy if using integer operations and careful loops (maybe 1-2 seconds?). But we also have two calls (for B and A-1). That's ~330 million transitions. Might be okay if optimized well. We can also use arrays from the array module or list comprehensions? But we need to update next_dp.
Alternatively, we could compress the remainder dimension by using loops over M but M is at most 500, that's fine.
We can implement DP as a list of dictionaries keyed by (prev,dir,rem) for each tight? Because many states may have count zero; but after some steps, many states become non-zero. But with M=500, prev 11, dir 3, that's 16500 combos, times tight 2 = 33000. In practice, many might be reachable, so using dense arrays may be faster than dictionary overhead.
Thus we can use a 4D list: dp[tight][prev][dir][rem]. Represent indices:
- tight: 0,1
- prev: 0..10 (10 means not started)
- dir: 0,1,2 (0 none, 1 increase, 2 decrease)
- rem: 0..M-1
Initialize dp[1][10][0][0] = 1.
For each digit in N_str: next_dp = a similar 4D list of zeros. For each tight in {0,1}: for prev in 0..10: for dir in 0..2: for rem in 0..M-1: cnt = dp[tight][prev][dir][rem] if cnt == 0: continue max_digit = digits[pos] if tight == 1 else 9 for d in range(0, max_digit+1): new_tight = 1 if (tight == 1 and d == max_digit) else 0 # Actually careful: if tight==1 and d == digits[pos] then new_tight remains 1; else if tight==1 and d < digits[pos] then new_tight=0; if tight==0 then new_tight=0. if tight == 1: new_tight = 1 if d == digits[pos] else 0 else: new_tight = 0 # transition: if prev == 10: # not started if d == 0: new_prev = 10 new_dir = 0 else: new_prev = d new_dir = 0 # allowed always new_rem = (rem * 10 + d) % M next_dp[new_tight][new_prev][new_dir][new_rem] = (next_dp[new_tight][new_prev][new_dir][new_rem] + cnt) % 10000 else: # started if d == prev: # equal digit not allowed continue direction = 1 if d > prev else 2 # 1 increase, 2 decrease if dir != 0 and direction == dir: # same direction consecutively not allowed continue new_prev = d new_dir = direction new_rem = (rem * 10 + d) % M next_dp[new_tight][new_prev][new_dir][new_rem] = (next_dp[new_tight][new_prev][new_dir][new_rem] + cnt) % 10000 dp = next_dp
After processing all digits, sum over all states where started (prev != 10) and rem == 0 (multiple of M). But careful: Are we counting the number 0? The state where prev == 10 (not started) corresponds to the number 0 (all zeros). We exclude it. Also we exclude numbers that are zero but not counted because they are not positive. So we sum over prev in 0..9, dir 0..2, tight 0 or 1 (both), rem=0.
That's count for numbers from 1 to N inclusive.
Now compute for B and A-1. Need to handle A-1 maybe 0; if A=1 then A-1=0, and count from 0 should be 0.
Implementation of A-1: we need to subtract 1 from the decimal string A. Since A can be up to 10^500, we need to do string subtraction to get A-1. That is straightforward: convert to list of digits, subtract 1 with borrowing.
Edge Cases: If A = 0? Not possible because A>=1. So A-1 >=0.
Now we have answer = (count(B) - count(A-1)) % 10000. Since we are mod 10000, we need to ensure positive.
Now let's test with examples.
Example 1: A=100, B=200, M=5. We compute count up to 200 minus count up to 99 (since A-1=99). Let's manually compute to see if we get 13.
We can try to simulate.
But before that, verify DP correctness for small numbers.
Potential issues:
- Our DP includes numbers with leading zeros that represent numbers with fewer digits. For example, when N=200 (len=3), numbers like 5 (single-digit) are represented as "005". But our DP: Starting state: not started, we place d=0 (leading zero) -> remain not started, remainder updates. Then eventually we place non-zero digit (like 5) and then continue possibly zeros. At end, we require started true. So "005" will be counted as started (since first non-zero is 5). But does it satisfy zigzag? For 5 (single digit), it's valid. Our DP when it places first non-zero digit (5) sets prev=5, dir=0. Then subsequent digits (zeros) after that: when we add next digit d=0, we check: prev=5, d=0 => d!=prev, direction=2 (decrease). Since dir=0, allowed. Then new_dir=2. Then next digit d=0? Wait 005: digits: 0,0,5? Actually representation is exactly 3 digits: we process from most significant to least: pos0=0, pos1=0, pos2=5? But to represent number 5, we would have digits: first two zeros, then 5. So the sequence: after first digit 0: not started; after second digit 0: still not started; after third digit 5: started with prev=5, dir=0, and that's end. So the number of digits placed after start is only one (the last digit). That's allowed. So counted correctly.
But what about number 10? Represented as "010"? Actually 10 is two-digit: digits 1 and 0. Represented as "010"? That would be digits: 0,1,0? Wait 10 in 3-digit representation: most significant digit 0, then 1, then 0. So we need to check DP: after first digit 0: not started; second digit 1: since d!=0, we start: prev=1, dir=0, rem updated; third digit 0: now prev=1, d=0, d!=prev, direction=2 (decrease). Since dir=0, it's allowed. So it's counted as two-digit number "10". That is zigzag? 1 then 0: decrease only, so valid. So counted.
But what about number 101? digits: 1,0,1. After first digit 1 (started), second digit 0 (direction decrease, dir=2), third digit 1 (direction increase, dir=1), allowed because previous dir=2, new dir=1 !=2. So valid.
Now check number with first digit zero? But the number must be positive, so first non-zero digit appears somewhere. That's fine.
Now, we must ensure that the DP does not count numbers that have a digit sequence that violates the alternation condition due to equality or repeated direction. Our transition covers that.
Now about numbers with length >=2 but all digits same? Not allowed because d != prev prevents equality.
Now about numbers that start with a non-zero digit and then later we have leading zeros? Actually zeros after start are fine.
Now, the DP counts numbers up to N inclusive. But we must be careful about numbers that have length less than len but whose digits when padded with leading zeros might be considered less than N? Since we treat the whole length with leading zeros, the numeric value is exactly the number, and it's always less than N because N has len digits and is at least 10^{len-1} > any number with fewer digits. However, one edge case: if N itself has leading zeros? No, N is given without leading zeros.
Thus DP works.
Now test example 1: A=100, B=200, M=5.
We'll compute count(200) - count(99). Let's manually compute using brute force for small numbers to confirm. But we trust.
Example 2: A=6, B=1234567, M=3 -> output 246.
We'll test after implementation.
Potential Performance Improvements:
- Use list comprehension to create dp arrays? We'll use nested lists. However with M up to 500, creating a 4D list each iteration could be heavy if done many times. But we can allocate two 4D arrays and reuse by resetting. However easier: create list of size 2, each containing a 3D list: for each tight, a list of 11 (prev) each containing list of 3 (dir) each containing list of M ints. That's 2113M = 33k ints. Creating such a list for each position (500 times) is 50033k ~ 16.5 million integer assignments, which is okay. But we can allocate two such structures and swap.
Alternative: Use a dictionary of state->count for each tight? But dense is likely faster.
-
Since we take mod 10000, we can store as ints mod 10000.
-
For loops: We'll loop over tight, prev, dir, rem. But we can skip states with cnt=0. That will save time if many states are zero. At start only few are non-zero. As we go, many become non-zero. Possibly all states become reachable. But we can still iterate all and check if cnt != 0, but still we have to iterate over all 33k states to check. That's fine.
-
For digit loops: we can precompute for each (prev, dir) the list of (new_prev, new_dir, allowed) per digit, but we also need to compute new_rem based on rem and digit, which we need to compute per rem anyway. So we can't precompute remainder updates because remainder depends on rem. However we can compute new_rem = (rem10 + d) % M. That is modulo multiplication and addition; we can precompute for each rem and digit the new remainder? Since M is up to 500, we can precompute a table next_rem[rem][d] = (rem10 + d) % M. That would speed up. Then we can iterate.
We can also precompute for each (prev, dir, d) whether transition is valid and the resulting (new_prev, new_dir). For prev=10 case (not started), it's always valid; transition determines new_prev and new_dir. For prev!=10, we need to check d != prev and direction condition. We can precompute a 11x3x10 table: valid[prev][dir][d] = (is_valid, new_prev, new_dir). For prev=10: if d==0 -> (True, 10, 0); else -> (True, d, 0). For prev in 0..9: if d == prev: invalid. else compute direction = 1 if d>prev else 2. if dir !=0 and direction == dir: invalid. else valid, new_prev = d, new_dir = direction.
We can store as tuple or separate arrays.
Then the DP loops: for each state (tight, prev, dir, rem) with cnt, determine digit range (if tight then 0..digit, else 0..9). For each d in that range, check if valid[prev][dir][d] is True; if yes, get new_prev, new_dir, compute new_rem = next_rem[rem][d], new_tight = tight and (d == digit)? Actually if tight==1, new_tight = (d == digit). Else 0. Then add cnt.
This should be efficient.
We also need to handle numbers that are exactly zero? Not counted.
Now the DP approach counts numbers from 0 to N inclusive, but we exclude 0 by ignoring started false at the end. So count(0) would return 0. For A-1 maybe 0, we handle by checking if A-1 is "0", then count(0)=0.
Implementation Steps:
- Read input: three lines A_str, B_str, M_str. Convert M=int(M_str).
- Define function count_up_to(N_str):
- If N_str == "0": return 0 (since no positive numbers <=0).
- digits = list of ints from N_str.
- L = len(digits)
- Initialize dp array: we can use a 4D list: dp = [ [ [ [0]*M for _ in range(3) ] for _ in range(11) ] for _ in range(2) ]
- dp[1][10][0][0] = 1
- Precompute next_rem[rem][d] for rem in 0..M-1, d in 0..9.
- Precompute trans_valid[prev][dir][d] = (is_valid, new_prev, new_dir) for prev in 0..10 (with 10 representing not started), dir in 0..2, d in 0..9.
- Then for each pos in range(L): next_dp = same sized structure (all zeros). digit = digits[pos] for tight in (0,1): for prev in range(11): for dir in range(3): row = dp[tight][prev][dir] # list of size M # we need to iterate over rem where row[rem]!=0; but to speed we can iterate all M and check if val !=0. for rem in range(M): cnt = row[rem] if cnt == 0: continue max_d = digit if tight else 9 for d in range(max_d+1): is_valid, new_prev, new_dir = trans[prev][dir][d] if not is_valid: continue new_t = tight and (d == digit) # careful: if tight is 1, new_t = 1 if d == digit else 0; if tight is 0, new_t remains 0 # Actually we compute: if tight == 1: new_tight = 1 if d == digit else 0; else new_tight = 0 if tight: new_tight = 1 if d == digit else 0 else: new_tight = 0 new_rem = next_rem[rem][d] next_dp[new_tight][new_prev][new_dir][new_rem] = (next_dp[new_tight][new_prev][new_dir][new_rem] + cnt) % 10000 dp = next_dp
- After processing all positions, result = sum over tight=0,1; over prev=0..9; over dir=0..2; dp[tight][prev][dir][0] % 10000. Return result.
We need to ensure that trans array for prev=10, dir (any) but dir only matters when prev=10? Actually for prev=10, dir is always 0 in the DP because we only set dir=0 for not started. But some states may have prev=10 and dir !=0? Could that happen? Starting state is (prev=10, dir=0). When prev=10, transitions: if d==0, remains prev=10, dir=0. If d!=0, becomes prev=d, dir=0. So dir always stays 0. So states with prev=10 and dir !=0 are unreachable. But we may still have them from initialization? Not. To be safe, we can still include them but they'll remain zero. So we can precompute trans for all dir values; for prev=10 we ignore dir, set same behavior (since direction not relevant). For prev!=10, we need to check dir condition; thus we need dir.
Now modulo: The counts may become large, but we mod 10000 at each addition.
Now we compute count_B = count_up_to(B_str) compute A_minus_1_str = decrement(A_str) if A_minus_1_str == "0": count_Aminus1 = 0 else count_Aminus1 = count_up_to(A_minus_1_str) answer = (count_B - count_Aminus1) % 10000 print(answer)
Now we must test with examples.
We'll implement decrement function:
def decrement(s): # s is string representing positive integer >=1 lst = list(s) i = len(lst)-1 while i >=0 and lst[i]=='0': lst[i]='9' i -= 1 if i <0: return "0" # shouldn't happen because s>=1 lst[i] = chr(ord(lst[i]) - 1) # remove leading zeros? result = ''.join(lst).lstrip('0') if result == '': return '0' return result
But careful: For A could be "1", then A-1 = "0". That's fine. For A= "100", decrement gives "099"? Actually our algorithm: lst = ['1','0','0']; i=2, lst[2]='0' => change to '9'? Wait 0 -> borrow: set to 9, i=1, lst[1]='0' -> set to '9', i=0, lst[0]='1' -> decrement to '0', then join gives "099". Then lstrip('0') => "99". That's correct. For A= "1000" -> decrement -> "0999" -> lstrip -> "999". Good.
Now test with example 1:
We'll simulate quickly maybe via code later, but let's manually compute small numbers to check DP logic.
But there may be pitfalls: The DP includes numbers with leading zeros, but also includes the number 0 (all zeros) when started false all the way and remainder 0. At the end we only sum states with prev != 10, so 0 excluded. Good.
Now check for numbers like 100: digits "100". Is 100 zigzag? digits 1,0,0: 1>0 decrease, 0==0 equal -> not allowed because equal digits. So 100 is not zigzag. In example 1, they listed numbers: 105,120,130,140,150,160,165,170,175,180,185,190,195. Those are all multiples of 5 between 100 and 200 and are zigzag. So 100 not included.
Now test DP for N=99 (A-1). For N=99 (len=2). Count up to 99 includes numbers 1..99. We need to compute count up to 200 minus count up to 99 should be 13.
Let's manually compute maybe small range 1..200 to verify quickly via brute? Could code but as reasoning, trust.
Now check example 2: Output 246. We'll trust.
Now complexity: 500 positions * 33k states * average digits ~5? Actually digits loop: for each state we loop d from 0 to max_digit. For tight=0, it's 10; for tight=1, it's digit+1, which average maybe 5. But worst-case if many states are tight=1? Actually dp[tight=1] states become fewer as we proceed; but we can't rely on that. But total operations ~165 million which is acceptable in PyPy if optimized. But we need to also loop over M (500) for each state; that's the inner loop. Actually we already accounted: number of states (tight, prev, dir, rem) = 2113*500 = 33,000. For each position, we iterate over all those states, and for each we iterate over digits. So operations per position = sum over states of digits. So roughly 33,000 * average digits (maybe 5-10) = 165k-330k per pos. Times 500 = 82.5M to 165M. Actually earlier I computed 33k * 10 = 330k per pos, times 500 = 165M. That's fine.
But note: In my loop nesting, I have for rem in range(M): check cnt. That means we loop over M=500 for each combination of tight, prev, dir. That's 2113=66 combos, each with 500 rem => 33k. Good.
Now implement trans table. We'll precompute as:
trans_valid = [[[False]*10 for _ in range(3)] for __ in range(11)] trans_new_prev = [[[0]*10 for _ in range(3)] for __ in range(11)] trans_new_dir = [[[0]*10 for _ in range(3)] for __ in range(11)]
Loop over prev in range(11): for dir in range(3): for d in range(10): if prev == 10: # not started if d == 0: new_prev = 10 new_dir = 0 else: new_prev = d new_dir = 0 valid = True else: