結果
問題 | No.260 世界のなんとか3 |
ユーザー | rpy3cpp |
提出日時 | 2015-12-09 16:54:15 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 4,703 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-11-07 18:09:55 |
合計ジャッジ時間 | 2,326 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
10,880 KB |
testcase_01 | AC | 31 ms
10,880 KB |
testcase_02 | AC | 34 ms
10,880 KB |
testcase_03 | AC | 38 ms
11,008 KB |
testcase_04 | AC | 39 ms
11,136 KB |
testcase_05 | AC | 32 ms
10,880 KB |
testcase_06 | AC | 31 ms
11,008 KB |
testcase_07 | AC | 36 ms
10,880 KB |
testcase_08 | AC | 34 ms
10,880 KB |
testcase_09 | AC | 32 ms
10,880 KB |
testcase_10 | AC | 36 ms
11,008 KB |
testcase_11 | AC | 37 ms
10,880 KB |
testcase_12 | AC | 34 ms
10,880 KB |
testcase_13 | AC | 31 ms
10,880 KB |
testcase_14 | AC | 35 ms
11,008 KB |
testcase_15 | AC | 32 ms
10,880 KB |
testcase_16 | AC | 35 ms
11,008 KB |
testcase_17 | AC | 35 ms
10,880 KB |
testcase_18 | AC | 34 ms
10,880 KB |
testcase_19 | AC | 35 ms
10,880 KB |
testcase_20 | AC | 33 ms
10,880 KB |
testcase_21 | AC | 33 ms
10,880 KB |
testcase_22 | AC | 36 ms
10,880 KB |
testcase_23 | AC | 32 ms
10,880 KB |
testcase_24 | AC | 34 ms
11,008 KB |
testcase_25 | AC | 41 ms
10,880 KB |
testcase_26 | AC | 37 ms
10,880 KB |
testcase_27 | AC | 31 ms
10,880 KB |
testcase_28 | AC | 46 ms
11,008 KB |
testcase_29 | AC | 54 ms
11,008 KB |
ソースコード
''' 解法: 0 から A までの数字を、10000個ごとに区切って考える。 すると、 下5桁以上の部分に 3 が含まれていれば、条件を満たすものは 8750 = 10000 * (1-1/8) 個あり、 下5桁以上の部分に 3 が含まれていなければ、条件をみたすものは 5000 個ある。 例: 1230000 から 1239999 には、条件を満たすものは 8750 個、 1240000 から 1249999 には、条件を満たすものは 5000 個ある。 したがって、0 から (A//10000) までに、3を含む数字が何個あるか ( = x とする) を数えれば、 8750 * x + 5000 * (A//10000) が条件を満たす個数となる。 10000 未満の端数については、ナイーブな方法で1つずつ数え上げていけばよい。 説明: 8 の倍数は下3桁のみで該当するか否かを判断できる。 下4桁目をバッファーとして使うと、10000個単位での条件を満たす数値の個数は、下から5桁目より上に3が含まれるか否かだけで決まる。 (1)5桁目より上に3が含まれている場合 8 の倍数でなければ、条件を満たす。よって、10000個のうち、7/8が条件を満たす。 (2)5桁目より上に3が含まれていない場合 (2.1)下4桁に3が含まれている場合 下4桁が8の倍数でなければ、条件を満たす。このような数の個数は、下4桁のみで決まり、5桁目より上の数に依存しない。 すなわち、10000 個単位でみた場合に、(2.1)のケースで条件を満たす個数は、5桁目より上の数によらず一定である。 (2.2)下4桁に3が含まれていない場合 8の倍数でなく、数値全体が3の倍数であれば、条件を満たす。 8の倍数か否かは下3桁で決まるので、5桁目より上の数値がいくつであるかは影響しない。 数値全体が3の倍数となるのは、各桁の数値の和が3の倍数となる場合である。 5桁目より上の各桁の数値の和を r 下3桁の各桁の数値の和を s 4桁目の数値を t とする。 t != 3 なので、t = {0,1,2,4,5,6,7,8,9} である。 すると、どのような (r, s) に対しても、(r + s + t) % 3 = 0 となる t を 3種類選ぶことができる。 たとえば、 (r + s) % 3 = 0 のときは、t = 0, 6, 9 を選ぶことができ、 (r + s) % 3 = 1 のときは、t = 2, 5, 8 を選ぶことができ、 (r + s) % 3 = 2 のときは、t = 1, 4, 7 を選ぶことができる。 すなわち、どのような r, s に対しても、条件を満たす(3の倍数となる)数を3つ作ることができる。 s がとりうるパターンは、rによらず一定なので、10000個単位でみると、(2.2)のケースで条件を満たす数の個数は、5桁目より上の数によらず、一定である。 (2.1), (2.2) より、(2)のケースで条件を満たすものの個数は、一定となる。 一定値が具体的にいくつであるかは、試しに計算してみれば分かる。 -> 5000 だった。 8 の倍数でなく、80の倍数、800の倍数のときも同様に、100,000個単位、1,000,000個単位で考えることができる。 ''' def solve(A, B): return (f(B) - f(A) + is_valid(A)) % (10**9 + 7) def is_valid(A): if len(A) < 4: a = int(A) return (('3' in A) or (a % 3 == 0)) and (a % 8 != 0) sumA = sum(map(int, A)) lowerA = int(A[-3:]) return (('3' in A) or (sumA % 3 == 0)) and (lowerA % 8 != 0) def f(A): return fcore(A, 8, 4, 8750, 3750) def f_naive(n, P, cum=0): cum %= 3 count = 0 for i in range(n + 1): if i % P == 0: continue if ('3' in str(i)) or ((i + cum) % 3 == 0): count += 1 return count def fcore(A, P, d, large, small): mod = 10**9 + 7 inv9 = 111111112 inv10 = 700000005 if len(A) <= d: return f_naive(int(A), P) head = A[:-d] tail = A[-d:] n = len(head) - 1 pow10 = pow(10, n, mod) pow9 = pow(9, n, mod) cum0 = 0 cum1 = 0 has_no_3 = True for a in head: m = ord(a) - 48 # ord('0') = 48 cum0 = (cum0 + pow10 * m) % mod pow10 = (pow10 * inv10) % mod if has_no_3: if m == 3: has_no_3 = False m -= m > 3 cum1 = (cum1 + pow9 * m) % mod pow9 = (pow9 * inv9) % mod if has_no_3: cum = sum(map(int, head)) return (large * cum0 - small * cum1 + f_naive(int(tail), P, cum)) % mod else: return (large * cum0 - small * cum1 + int(tail) - int(tail)//P) % mod A, B = input().split() print(solve(A, B))