結果
| 問題 |
No.315 世界のなんとか3.5
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-20 20:26:13 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,254 bytes |
| コンパイル時間 | 329 ms |
| コンパイル使用メモリ | 82,372 KB |
| 実行使用メモリ | 91,512 KB |
| 最終ジャッジ日時 | 2025-03-20 20:27:36 |
| 合計ジャッジ時間 | 4,950 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 12 TLE * 1 -- * 23 |
ソースコード
MOD = 10**9 + 7
def subtract_one(s):
s_list = list(s)
i = len(s_list) - 1
while i >= 0 and s_list[i] == '0':
s_list[i] = '9'
i -= 1
if i < 0:
return '0' # shouldn't happen per problem constraints
s_list[i] = str(int(s_list[i]) - 1)
if s_list[i] == '0' and i == 0 and len(s_list) > 1:
# Check if leading zero and length >1
# return the string as is, the DP will handle leading zeros
pass
return ''.join(s_list)
def count_aho(upper):
n = len(upper)
current_dp = [[[[0]*2 for _ in range(2)] for __ in range(2)] for ___ in range(3)]
current_dp[0][0][1][1] = 1 # sum_mod, has_three, leading_zero, tight
for i in range(n):
next_dp = [[[[0]*2 for _ in range(2)] for __ in range(2)] for ___ in range(3)]
limit = int(upper[i])
for sum_mod in range(3):
for has_t in range(2):
for leading in range(2):
for tight in range(2):
cnt = current_dp[sum_mod][has_t][leading][tight]
if cnt == 0:
continue
max_d = limit if tight else 9
for d in range(0, max_d+1):
new_tight = tight and (d == max_d)
new_leading = leading and (d == 0)
new_sum = sum_mod
new_has = has_t
if not new_leading:
new_sum = (sum_mod + d) % 3
if d == 3:
new_has = 1
else:
new_sum = 0
new_has = 0
next_dp[new_sum][new_has][new_leading][new_tight] = (
next_dp[new_sum][new_has][new_leading][new_tight] + cnt
) % MOD
current_dp = next_dp
total = 0
for sum_mod in range(3):
for has_t in range(2):
for leading in range(2):
for tight in range(2):
if leading:
continue
if sum_mod == 0 or has_t == 1:
total = (total + current_dp[sum_mod][has_t][leading][tight]) % MOD
return total
def count_aho_div_p(upper, P):
n = len(upper)
current_dp = [[[[[0]*2 for _ in range(2)] for __ in range(P)] for ___ in range(2)] for ____ in range(3)]
current_dp[0][0][0][1][1] = 1 # sum_mod, has_3, mod_p, leading, tight
for i in range(n):
next_dp = [[[[[0]*2 for _ in range(2)] for __ in range(P)] for ___ in range(2)] for ____ in range(3)]
limit = int(upper[i])
for sum_mod in range(3):
for has_t in range(2):
for mod_p in range(P):
for leading in range(2):
for tight in range(2):
cnt = current_dp[sum_mod][has_t][mod_p][leading][tight]
if cnt == 0:
continue
max_d = limit if tight else 9
for d in range(0, max_d+1):
new_tight = tight and (d == max_d)
new_leading = leading and (d == 0)
new_sum = sum_mod
new_has = has_t
new_mod = mod_p
if not new_leading:
new_sum = (sum_mod + d) % 3
if d ==3:
new_has = 1
new_mod = (mod_p * 10 + d) % P
else:
new_sum = 0
new_has = 0
new_mod = 0 # still leading zero, mod is 0
next_dp[new_sum][new_has][new_mod][new_leading][new_tight] = (
next_dp[new_sum][new_has][new_mod][new_leading][new_tight] + cnt
) % MOD
current_dp = next_dp
total = 0
for sum_mod in range(3):
for has_t in range(2):
for mod_p in range(P):
for leading in range(2):
for tight in range(2):
if leading:
continue
if (sum_mod ==0 or has_t ==1) and mod_p ==0:
total = (total + current_dp[sum_mod][has_t][mod_p][leading][tight]) % MOD
return total
def solve():
import sys
input = sys.stdin.read().split()
A = input[0]
B = input[1]
P = int(input[2])
A_minus_1 = subtract_one(A)
fB = count_aho(B)
fA_1 = count_aho(A_minus_1) if A != '0' else 0
total_aho = (fB - fA_1) % MOD
gB = count_aho_div_p(B, P)
gA_1 = count_aho_div_p(A_minus_1, P) if A != '0' else 0
total_aho_div_p = (gB - gA_1) % MOD
ans = (total_aho - total_aho_div_p) % MOD
print(ans)
if __name__ == '__main__':
solve()