結果
| 問題 |
No.315 世界のなんとか3.5
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:04:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,837 bytes |
| コンパイル時間 | 394 ms |
| コンパイル使用メモリ | 82,788 KB |
| 実行使用メモリ | 277,980 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:09 |
| 合計ジャッジ時間 | 5,726 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 12 MLE * 1 -- * 23 |
ソースコード
import sys
# Increase recursion depth limit for potentially very long numbers.
# The maximum length of A and B is 200000 according to the problem statement.
# Setting it slightly higher for safety margin.
# Note: On some systems or platforms, the maximum recursion depth might be limited by OS.
# Competitive programming platforms usually allow high limits.
try:
sys.setrecursionlimit(200000 + 10)
except OverflowError:
# If setting the limit causes an OverflowError (rare, possibly due to system constraints)
# fall back to a default large value. Adjust if needed based on platform specifics.
sys.setrecursionlimit(2000)
MOD = 10**9 + 7
# Memoization dictionary to store results of DP states
memo = {}
# Input number N as a string, used by the DP function
S = ""
# Divisor P, given in the input (8, 80, or 800)
P = 0
# The core digit DP function
# Arguments:
# idx: current digit index being processed (from left, 0-based)
# tight: boolean flag, True if we are restricted by the digits of N, False otherwise
# is_leading_zero: boolean flag, True if we are currently placing leading zeros
# has_digit_3: boolean flag, True if any digit '3' has been placed so far (ignoring leading zeros)
# rem_3: the remainder of the number formed so far when divided by 3
# rem_P: the remainder of the number formed so far when divided by P
def dp(idx, tight, is_leading_zero, has_digit_3, rem_3, rem_P):
# Base case: If we have processed all digits
if idx == len(S):
# If the number constructed consists of only leading zeros (effectively the number 0)
# it doesn't satisfy the condition A >= 1. We count numbers in [1, N].
# So, return 0 for the number 0.
if is_leading_zero:
return 0
# Check the conditions specified in the problem:
# Condition "Aho": number is multiple of 3 OR contains digit 3
is_aho = (rem_3 == 0) or has_digit_3
# Condition "Hajirai": number is multiple of P
is_hajirai = (rem_P == 0)
# We need numbers that are "Aho" AND NOT "Hajirai"
if is_aho and not is_hajirai:
return 1 # Count this number
else:
return 0 # Do not count this number
# Create a tuple representing the current state for memoization key
state = (idx, tight, is_leading_zero, has_digit_3, rem_3, rem_P)
# Check if the result for this state is already computed and stored in memo
if state in memo:
return memo[state]
# Initialize the result for the current state to 0
res = 0
# Determine the upper limit for the current digit 'd'
# If 'tight' is True, limit is the digit S[idx], otherwise it's 9
limit = int(S[idx]) if tight else 9
# Iterate through all possible digits 'd' for the current position 'idx'
for d in range(limit + 1):
# Determine the 'tight' constraint for the next recursive call
# It remains True only if the current 'tight' is True AND we chose the maximum possible digit 'd'
new_tight = tight and (d == limit)
# Store current remainders before potential updates. This helps clarify logic especially
# when transitioning from leading zero state.
current_rem_3 = rem_3
current_rem_P = rem_P
# Handle the case where we are currently placing leading zeros
if is_leading_zero and d == 0:
# If current digit is 0 and we were placing leading zeros, we continue doing so.
# The state related to digit 3 and remainders doesn't change substantively (remains 0).
# The 'has_digit_3' flag remains False.
res = (res + dp(idx + 1, new_tight, True, False, 0, 0)) % MOD
else:
# If current digit 'd' is non-zero, or if we were already past the leading zeros phase:
# If we are placing the first non-zero digit (transitioning from leading zero state)
if is_leading_zero:
# The previous number value was 0, so start remainders based on 'd'
current_rem_3 = 0
current_rem_P = 0
# The number is no longer considered zero. Update state accordingly.
new_is_leading_zero = False # We are past leading zeros now
# Update the has_digit_3 flag: True if it was already True, or if the current digit 'd' is 3.
new_has_digit_3 = has_digit_3 or (d == 3)
# Calculate the new remainder modulo 3
new_rem_3 = (current_rem_3 * 10 + d) % 3
# Calculate the new remainder modulo P
new_rem_P = (current_rem_P * 10 + d) % P
# Recursively call the DP function for the next digit position (idx + 1)
# with updated state variables, and add the returned count to 'res'.
res = (res + dp(idx + 1, new_tight, new_is_leading_zero, new_has_digit_3, new_rem_3, new_rem_P)) % MOD
# Store the computed result for the current state in the memoization table
memo[state] = res
return res
# Function to compute F(N): the count of numbers x such that 1 <= x <= N
# satisfying the conditions (Aho and not Hajirai).
def solve(N_str):
global S, memo, P # Need access to global variables S, memo, P
S = N_str
# Clear the memoization table for each new call to solve() with a different N
memo = {}
# Handle edge cases: if N_str represents 0 or is empty.
# The problem constraints state A >= 1, so N will be at least '1' for F(B),
# and at least '0' for F(A-1). F(0) is 0.
if not S or S == '0':
return 0
# Initial call to the DP function:
# Start at index 0.
# 'tight' is True because we are constrained by the digits of N.
# 'is_leading_zero' is True initially.
# 'has_digit_3' is False initially.
# 'rem_3' and 'rem_P' are 0 initially.
return dp(0, True, True, False, 0, 0)
# Function to subtract 1 from a number represented as a string.
# Handles large numbers that don't fit into standard integer types.
def subtract_one(N_str):
# If input is "0", subtracting 1 is not defined in positive integers context.
# But for calculating F(A-1), if A=1, A-1=0. We handle F(0) directly.
# This function should return "0" when input is "1".
if N_str == '1': return "0"
if N_str == '0': return "0" # Defensive check, F(0)=0 handled in main logic
n = len(N_str)
num = list(N_str)
i = n - 1
# Standard subtraction algorithm (borrowing from left)
while i >= 0:
if num[i] == '0':
num[i] = '9' # Borrow: change '0' to '9'
i -= 1 # Move left to borrow
else:
num[i] = str(int(num[i]) - 1) # Subtract 1 from non-zero digit
break # Borrowing chain stops
# If the subtraction resulted in a leading zero (e.g., "100" -> "099")
# and the number has more than one digit.
if num[0] == '0' and n > 1:
# Return the string without the leading zero
return "".join(num[1:])
else:
# Otherwise return the resulting string (handles single digits correctly, e.g., "1" -> "0")
return "".join(num)
# Read input using sys.stdin.readline for potentially faster I/O than input()
A_str, B_str, P_str = sys.stdin.readline().split()
P = int(P_str)
# Calculate F(B), the count of valid numbers up to B
count_B = solve(B_str)
# Calculate the string representation of A-1
A_minus_1_str = subtract_one(A_str)
# Calculate F(A-1), the count of valid numbers up to A-1
# The solve function correctly handles N_str = "0" by returning 0.
count_A_minus_1 = solve(A_minus_1_str)
# The final answer is F(B) - F(A-1).
# Compute the result modulo MOD. Add MOD before taking modulo to handle potential negative result.
ans = (count_B - count_A_minus_1 + MOD) % MOD
print(ans)