結果
問題 | No.260 世界のなんとか3 |
ユーザー | takeya_okino |
提出日時 | 2019-06-27 19:23:07 |
言語 | Java21 (openjdk 21) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,936 bytes |
コンパイル時間 | 2,548 ms |
コンパイル使用メモリ | 74,528 KB |
実行使用メモリ | 93,660 KB |
最終ジャッジ日時 | 2023-09-10 20:00:01 |
合計ジャッジ時間 | 18,562 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 117 ms
55,720 KB |
testcase_01 | AC | 118 ms
55,916 KB |
testcase_02 | AC | 116 ms
56,208 KB |
testcase_03 | MLE | - |
testcase_04 | MLE | - |
testcase_05 | MLE | - |
testcase_06 | MLE | - |
testcase_07 | MLE | - |
testcase_08 | MLE | - |
testcase_09 | MLE | - |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | AC | 311 ms
62,432 KB |
testcase_14 | MLE | - |
testcase_15 | MLE | - |
testcase_16 | MLE | - |
testcase_17 | MLE | - |
testcase_18 | MLE | - |
testcase_19 | MLE | - |
testcase_20 | MLE | - |
testcase_21 | MLE | - |
testcase_22 | MLE | - |
testcase_23 | AC | 219 ms
61,976 KB |
testcase_24 | MLE | - |
testcase_25 | MLE | - |
testcase_26 | MLE | - |
testcase_27 | AC | 116 ms
55,656 KB |
testcase_28 | MLE | - |
testcase_29 | MLE | - |
ソースコード
import java.util.*; public class Main { public static long MOD = (long)Math.pow(10, 9) + 7; public static void main(String[] args) { Scanner sc = new Scanner(System.in); String A = sc.next(); String B = sc.next(); long ans = 0; if(A.equals("1")) { ans = func(B); } else { ans = (func(B) - func(A) + MOD) % MOD; int p1 = 0; int p2 = 0; int sum = 0; for(int i = 0; i < A.length(); i++) { int a = Integer.parseInt(String.valueOf(A.charAt(i))); if(a == 3) p1 = 1; sum += a; } if(sum % 3 == 0) p1 = 1; String a = A; if(A.length() > 3) a = A.substring(A.length() - 3); int an = Integer.parseInt(a); if((an % 8) != 0) p2 = 1; if((p1 == 1) && (p2 == 1)) ans = (ans + 1) % MOD; } System.out.println(ans); } public static long func(String X) { int len = X.length(); long[][][][][] dp2 = new long[len][3][2][8][2]; int first = Integer.parseInt(String.valueOf(X.charAt(0))); for(int j = 0; j <= first; j++) { if(j == first) { if(j == 3) { dp2[0][j % 3][1][j % 8][0]++; } else { dp2[0][j % 3][0][j % 8][0]++; } } else { if(j == 3) { dp2[0][j % 3][1][j % 8][1]++; } else { dp2[0][j % 3][0][j % 8][1]++; } } } for(int i = 1; i < len; i++) { int d = Integer.parseInt(String.valueOf(X.charAt(i))); for(int j = 0; j < 3; j++) { for(int l = 0; l < 8; l++) { for(int k = 0; k <= d; k++) { if(k == d) { if(k == 3) { dp2[i][(j + k) % 3][1][(10 * l + k) % 8][0] = (dp2[i][(j + k) % 3][1][(10 * l + k) % 8][0] + dp2[i - 1][j][0][l][0]) % MOD; } else { dp2[i][(j + k) % 3][0][(10 * l + k) % 8][0] = (dp2[i][(j + k) % 3][0][(10 * l + k) % 8][0] + dp2[i - 1][j][0][l][0]) % MOD; } } else { if(k == 3) { dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] = (dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] + dp2[i - 1][j][0][l][0]) % MOD; } else { dp2[i][(j + k) % 3][0][(10 * l + k) % 8][1] = (dp2[i][(j + k) % 3][0][(10 * l + k) % 8][1] + dp2[i - 1][j][0][l][0]) % MOD; } } } } } for(int j = 0; j < 3; j++) { for(int l = 0; l < 8; l++) { for(int k = 0; k < 10; k++) { if(k == 3) { dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] = (dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] + dp2[i - 1][j][0][l][1]) % MOD; } else { dp2[i][(j + k) % 3][0][(10 * l + k) % 8][1] = (dp2[i][(j + k) % 3][0][(10 * l + k) % 8][1] + dp2[i - 1][j][0][l][1]) % MOD; } } } } for(int j = 0; j < 3; j++) { for(int l = 0; l < 8; l++) { for(int k = 0; k <= d; k++) { if(k == d) { dp2[i][(j + k) % 3][1][(10 * l + k) % 8][0] = (dp2[i][(j + k) % 3][1][(10 * l + k) % 8][0] + dp2[i - 1][j][1][l][0]) % MOD; } else { dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] = (dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] + dp2[i - 1][j][1][l][0]) % MOD; } } } } for(int j = 0; j < 3; j++) { for(int l = 0; l < 8; l++) { for(int k = 0; k < 10; k++) { dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] = (dp2[i][(j + k) % 3][1][(10 * l + k) % 8][1] + dp2[i - 1][j][1][l][1]) % MOD; } } } } long ans = 0; for(int m = 0; m < 2; m++) { for(int l = 1; l < 8; l++) { for(int k = 0; k < 2; k++) { if(k == 0) { ans = (ans + dp2[len - 1][0][k][l][m]) % MOD; } else { for(int j = 0; j < 3; j++) { ans = (ans + dp2[len - 1][j][k][l][m]) % MOD; } } } } } return ans; } }