結果
問題 | No.315 世界のなんとか3.5 |
ユーザー | Min_25 |
提出日時 | 2015-12-08 15:55:55 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 290 ms / 2,000 ms |
コード長 | 1,718 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 10,916 KB |
実行使用メモリ | 9,036 KB |
最終ジャッジ日時 | 2023-10-12 21:56:46 |
合計ジャッジ時間 | 5,364 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
8,176 KB |
testcase_01 | AC | 16 ms
8,064 KB |
testcase_02 | AC | 30 ms
8,388 KB |
testcase_03 | AC | 16 ms
7,996 KB |
testcase_04 | AC | 17 ms
8,064 KB |
testcase_05 | AC | 19 ms
8,096 KB |
testcase_06 | AC | 30 ms
8,344 KB |
testcase_07 | AC | 19 ms
8,164 KB |
testcase_08 | AC | 20 ms
8,172 KB |
testcase_09 | AC | 17 ms
8,168 KB |
testcase_10 | AC | 16 ms
8,168 KB |
testcase_11 | AC | 17 ms
8,100 KB |
testcase_12 | AC | 61 ms
8,420 KB |
testcase_13 | AC | 61 ms
8,460 KB |
testcase_14 | AC | 104 ms
8,512 KB |
testcase_15 | AC | 101 ms
8,612 KB |
testcase_16 | AC | 105 ms
8,612 KB |
testcase_17 | AC | 109 ms
8,496 KB |
testcase_18 | AC | 65 ms
8,432 KB |
testcase_19 | AC | 64 ms
8,568 KB |
testcase_20 | AC | 103 ms
8,804 KB |
testcase_21 | AC | 103 ms
8,708 KB |
testcase_22 | AC | 142 ms
8,608 KB |
testcase_23 | AC | 146 ms
8,564 KB |
testcase_24 | AC | 109 ms
8,580 KB |
testcase_25 | AC | 142 ms
8,512 KB |
testcase_26 | AC | 108 ms
8,496 KB |
testcase_27 | AC | 104 ms
8,612 KB |
testcase_28 | AC | 172 ms
8,680 KB |
testcase_29 | AC | 255 ms
8,880 KB |
testcase_30 | AC | 223 ms
8,968 KB |
testcase_31 | AC | 220 ms
9,036 KB |
testcase_32 | AC | 234 ms
8,968 KB |
testcase_33 | AC | 145 ms
8,676 KB |
testcase_34 | AC | 288 ms
8,900 KB |
testcase_35 | AC | 290 ms
8,976 KB |
ソースコード
def prob315(): MOD = 10 ** 9 + 7 def count(A, p, e, inclusive, MOD=MOD): prefix = 0 has3 = False f, s = 0, 0 mid = max(0, len(A) - 4 - e) for i in range(mid): # xrange d = ord(A[i]) - 0x30 f = (f * 10 + s) % MOD s = (s * 9) % MOD if has3: f = (f + d) % MOD else: s = (s + d - (d > 3)) % MOD f = (f + (d > 3)) % MOD prefix = (prefix + d) % 3 has3 |= d == 3 p3 = 3 * p curr = [0] * (4 * p) curr[0] = curr[1] = curr[2] = s * pow(3, MOD - 2, MOD) % MOD curr[p3] = f for i in range(mid, len(A)): next = [0] * (4 * p) d = ord(A[i]) - 0x30 for r in range(p3): if not curr[r]: continue for j in range(10): k = (p3 + (r * 10 + j) % p) if j == 3 else (r * 10 + j) % p3 next[k] = (next[k] + curr[r]) % MOD for r in range(p): if not curr[p3 + r]: continue for j in range(10): k = p3 + (r * 10 + j) % p next[k] = (next[k] + curr[p3 + r]) % MOD for j in range(d): k = p3 + (prefix * 10 + j) % p if (j == 3 or has3) else (prefix * 10 + j) % p3 next[k] = (next[k] + 1) % MOD prefix = (prefix * 10 + d) % p3 has3 |= d == 3 curr = next if inclusive: k = p3 + prefix % p if has3 else prefix curr[k] = (curr[k] + 1) % MOD ret = sum(c for i, c in enumerate(curr[:p3]) if i % 3 == 0 and i % p != 0) ret += sum(curr[p3+1:]) return ret % MOD import sys rl = sys.stdin.readline A, B, P = rl().split() P = int(P) e = 0 while P % 10 ** (e + 1) == 0: e += 1 a = count(A, P, e, False) b = count(B, P, e, True) print((b - a) % MOD) prob315()