Submission #28135

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.*;
class Main {
static final long MOD = 1000000007;
static long calculate(int[] digits, int k) {
int n = digits.length;
// dp[i] ha [0, i) ketame miman de k wo hukumanai monono kosuu
long[] dp = new long[n + 1];
dp[0] = 0;
boolean kAppeared = false;
for (int i = 0; i < n; ++i) {
dp[i + 1] = (9 * dp[i]) % MOD;
if (!kAppeared) {
if (digits[i] > k) {
dp[i + 1] = (dp[i + 1] + digits[i] - 1) % MOD;
} else {
dp[i + 1] = (dp[i + 1] + digits[i]) % MOD;
}
}
if (digits[i] == k) {
kAppeared = true;
}
if (k == 0 && i >= 1) {
dp[i + 1] = (dp[i + 1] + 9) % MOD;
}
}
long a = 0;
for (int i = 0; i < n; ++i) {
a = (10 * a + digits[i]) % MOD;
}
return (a + MOD - dp[n]) % MOD;
}
static int[] toDigits(String number) {
int[] answer = new int[number.length()];
for (int i = 0; i < answer.length; ++i) {
answer[i] = (int) number.charAt(i) - 48;
}
return answer;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String a = scan.next();
String b = scan.next();
int k = scan.nextInt();
int[] aDigits = toDigits(a);
int[] bDigits = toDigits(b);
// a wo 1 herasu
int position;
for (position = bDigits.length - 1; position >= 0; --position) {
bDigits[position] += 1;
if (bDigits[position] >= 10) {
bDigits[position] -= 10;
continue;
}
break;
}
if (position == -1 && bDigits[0] == 0) {
int[] newB = new int[bDigits.length + 1];
newB[0] = 1;
for (int i = 0; i < bDigits.length; ++i) {
newB[i + 1] = bDigits[i];
}
bDigits = newB;
}
long result = calculate(bDigits, k);
result = (result + MOD - calculate(aDigits, k)) % MOD;
System.out.println(result);
}
}

ステータス

項目 データ
問題 0565 - 桁
ユーザー名 KirikaYuumura
投稿日時 2017-10-28 17:37:08
言語 Java
状態 Accepted
得点 2
ソースコード長 1829 Byte
最大実行時間 106 ms
最大メモリ使用量 19920 KB

セット

セット 得点 Cases
1 SMALL 1 / 1 *small*
2 LARGE 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00.in AC 103 ms 19756 KB
2
00large.in AC 91 ms 19560 KB
2
00sample.in AC 73 ms 13716 KB
2
00small.in AC 67 ms 14684 KB
1
2
01.in AC 99 ms 18284 KB
2
01large.in AC 106 ms 16588 KB
2
01sample.in AC 64 ms 14540 KB
2
01small.in AC 91 ms 14816 KB
1
2
02.in AC 93 ms 19736 KB
2
02large.in AC 93 ms 16316 KB
2
02sample.in AC 67 ms 13280 KB
2
02small.in AC 73 ms 14616 KB
1
2
03.in AC 95 ms 18580 KB
2
03large.in AC 89 ms 16512 KB
2
03small.in AC 65 ms 13840 KB
1
2
04.in AC 96 ms 19056 KB
2
04large.in AC 91 ms 17060 KB
2
04small.in AC 80 ms 14552 KB
1
2
05.in AC 96 ms 19920 KB
2
05large.in AC 93 ms 16916 KB
2
05small.in AC 73 ms 14392 KB
1
2
06.in AC 100 ms 19060 KB
2
06large.in AC 91 ms 17724 KB
2
06small.in AC 69 ms 14920 KB
1
2
07.in AC 89 ms 19600 KB
2
07large.in AC 87 ms 16364 KB
2
07small.in AC 68 ms 14880 KB
1
2
08.in AC 93 ms 19896 KB
2
08large.in AC 86 ms 19548 KB
2
08small.in AC 72 ms 13352 KB
1
2
09.in AC 91 ms 18536 KB
2
09large.in AC 91 ms 17756 KB
2
09small.in AC 69 ms 13664 KB
1
2