結果
| 問題 | No.315 世界のなんとか3.5 |
| ユーザー |
 Grenache
|
| 提出日時 | 2015-12-09 01:26:41 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,286 ms / 2,000 ms |
| コード長 | 4,725 bytes |
| コンパイル時間 | 3,802 ms |
| コンパイル使用メモリ | 78,500 KB |
| 実行使用メモリ | 48,448 KB |
| 最終ジャッジ日時 | 2024-09-14 20:52:02 |
| 合計ジャッジ時間 | 22,224 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
ソースコード
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_yukicoder315 {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 = sc.nextInt();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;static final int DMAX = 5;private static int aho(char[] b, int p) {int n = b.length;if (mod8 == null) {mod8 = new int[DMAX ];int mod = 1;for (int i = 0; i < DMAX; i++) {mod8[i] = mod % p;mod *= 10;}}int d = 3;int[][][][] dp = new int[2][2][d][p];int[][][][] dp2 = new int[2][2][d][p];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';int nowj = (j - 1) % 2;int nextj = j % 2;for (int l = 0; l < 2; l++) {for (int i = 0; i < d; i++) {Arrays.fill(dp[nextj][l][i], 0);Arrays.fill(dp2[nextj][l][i], 0);}}for (int l = 0; l < 2; l++) {for (int i = 0; i < d; i++) {for (int k = 0; k < 10; k++) {int nextl = l;if (k == 3) {nextl = 1;}int nexti = (i + k) % d;if (j <= DMAX) {for (int i8 = 0; i8 < p; i8++) {int nexti8 = (i8 + k * mod8[j - 1]) % p;dp[nextj][nextl][nexti][nexti8] += dp[nowj][l][i][i8];dp[nextj][nextl][nexti][nexti8] %= MOD;if (k == num) {dp2[nextj][nextl][nexti][nexti8] += dp2[nowj][l][i][i8];dp2[nextj][nextl][nexti][nexti8] %= MOD;} else if (k < num) {dp2[nextj][nextl][nexti][nexti8] += dp[nowj][l][i][i8];dp2[nextj][nextl][nexti][nexti8] %= MOD;}}} else {int i8 = 0;int nexti8 = 0;dp[nextj][nextl][nexti][nexti8] += dp[nowj][l][i][i8];dp[nextj][nextl][nexti][nexti8] %= MOD;if (k == num) {dp2[nextj][nextl][nexti][nexti8] += dp2[nowj][l][i][i8];dp2[nextj][nextl][nexti][nexti8] %= MOD;} else if (k < num) {dp2[nextj][nextl][nexti][nexti8] += dp[nowj][l][i][i8];dp2[nextj][nextl][nexti][nexti8] %= MOD;}}}}}if (j == DMAX) {for (int l = 0; l < 2; l++) {for (int i = 0; i < d; i++) {for (int k = 0; k < 10; k++) {dp[nextj][l][i][0] = 0;dp2[nextj][l][i][0] = 0;for (int i8 = 1; i8 < p; i8++) {dp[nextj][l][i][0] += dp[nextj][l][i][i8];dp[nextj][l][i][0] %= MOD;dp2[nextj][l][i][0] += dp2[nextj][l][i][i8];dp2[nextj][l][i][0] %= MOD;}}}}}}int ret = 0;for (int l = 0; l < 2; l++) {for (int i = 0; i < d; i++) {if (n <= DMAX) {for (int i8 = 0; i8 < p; i8++) {if ((l == 1 || i == 0) && i8 != 0) {ret += dp2[n % 2][l][i][i8];ret %= MOD;}}} else {if ((l == 1 || i == 0)) {ret += dp2[n % 2][l][i][0];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);}}}