結果
| 問題 | No.260 世界のなんとか3 |
| ユーザー |
 Grenache
|
| 提出日時 | 2015-12-08 23:30:15 |
| 言語 | Java (openjdk 23) |
| 結果 |
MLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 3,984 bytes |
| コンパイル時間 | 6,604 ms |
| コンパイル使用メモリ | 78,824 KB |
| 実行使用メモリ | 67,084 KB |
| 最終ジャッジ日時 | 2024-12-20 17:59:04 |
| 合計ジャッジ時間 | 17,901 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 MLE * 4 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.Iterator;public class Main_yukicoder260 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);char[] a = sc.next().toCharArray();char[] b = sc.next().toCharArray();int p = 0;int ret = (aho(b, p) - aho(sub(a, '1'), p) + MOD) % MOD;pr.println(ret);pr.close();sc.close();}static final int MOD = 1_000_000_007;static int[] mod8;private static int aho(char[] b, int p) {int n = b.length;if (mod8 == null) {mod8 = new int[10_000 + 1];int mod = 1;for (int i = 0; i <= 10_000; i++) {mod8[i] = mod % 8;mod *= 10;}}int d = 3;int[][][][] dp = new int[2][d][8][n + 1];int[][][][] dp2 = new int[2][d][8][n + 1];dp[0][0][0][0] = 1;dp2[0][0][0][0] = 1;for (int j = 1; j <= n; j++) {int num = b[n - j] - '0';for (int l = 0; l < 2; l++) {for (int i = 0; i < d; i++) {for (int i8 = 0; i8 < 8; i8++) {for (int k = 0; k < 10; k++) {if (k != 3) {dp[l][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] += dp[l][i][i8][j - 1];dp[l][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] %= MOD;} else {dp[1][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] += dp[l][i][i8][j - 1];dp[1][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] %= MOD;}if (k == num) {if (k != 3) {dp2[l][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] += dp2[l][i][i8][j - 1];dp2[l][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] %= MOD;} else {dp2[1][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] += dp2[l][i][i8][j - 1];dp2[1][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] %= MOD;}} else if (k < num) {if (k != 3) {dp2[l][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] += dp[l][i][i8][j - 1];dp2[l][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] %= MOD;} else {dp2[1][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] += dp[l][i][i8][j - 1];dp2[1][(i + k) % d][(i8 + k * mod8[j - 1]) % 8][j] %= MOD;}}}}}}}int ret = 0;for (int l = 0; l < 2; l++) {for (int i = 0; i < d; i++) {for (int i8 = 0; i8 < 8; i8++) {if ((l == 1 || i == 0) && i8 != 0) {ret += dp2[l][i][i8][n];ret %= MOD;}}}}return ret;}private static char[] sub(char[] a, char c) {for (int i = a.length - 1; i >= 0; i--) {if (a[i] - c < 0) {a[i] = (char)(a[i] - c + 10 + '0');c = '1';} else {a[i] = (char)(a[i] - c + '0');break;}}return a;}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}