結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー 37zigen
提出日時 2016-08-25 23:53:00
言語 Java
(openjdk 23)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,016 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,264 ms
コンパイル使用メモリ 87,404 KB
実行使用メモリ 88,396 KB
最終ジャッジ日時 2024-11-08 04:07:13
合計ジャッジ時間 19,708 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other MLE * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package No200番台;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;

public class Q260 {
	public static void main(String[] args) throws Exception {
		new Q260().run();
	}

	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";

	public void run() throws Exception {

		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		Thread t = new Thread(null, null, "name", Runtime.getRuntime().maxMemory()) {
			@Override
			public void run() {
				solver();
				out.flush();
			}
		};
		t.start();
		t.join();
	}

	long MOD = 1_000_000_000 + 7;

	String subject = "";

	void solver() {
		String a = ns();
		String b = ns();
		while (a.length() > b.length())
			b = "0" + b;
		while (b.length() > a.length())
			a = "0" + a;
		long ans = ((f(b) - f(a) % MOD + is_sol(a)) % MOD + MOD) % MOD;
		out.println(ans);
	}

	int is_sol(String s) {
		int mod3 = 0;
		int mod8 = 0;
		boolean three = false;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '3') {
				three = true;
			}
		}
		for (int i = 0; i < s.length(); i++) {
			mod3 = (mod3 + (s.charAt(i) - '0')) % 3;
		}
		for (int i = Math.max(s.length() - 4, 0); i < s.length(); i++) {
			mod8 = (mod8 * 10 + (s.charAt(i) - '0')) % 8;
		}
		return ((three || mod3 == 0) && mod8 != 0) ? 1 : 0;
	}

	long f(String s) {
		subject = s;
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				for (int k = 0; k < dp[0][0].length; k++) {
					for (int l = 0; l < dp[0][0][0].length; l++) {
						for (int m = 0; m < dp[0][0][0][0].length; m++) {
							dp[i][j][k][l][m] = -1;
						}
					}
				}
			}
		}
		return dfs(0, 0, 0, 1, 0);
	}

	// Here, 1 is dealed as an identifier of TRUE。
	long dfs(int digits_number, int mod3, int mod8, int lim, int three) {
		if (digits_number == subject.length()) {
			return ((mod3 == 0 || three == 1) && mod8 != 0) ? 1 : 0;
		}
		if (dp[digits_number][mod3][mod8][lim][three] != -1) {
			return dp[digits_number][mod3][mod8][lim][three];
		}
		int ans = 0;
		for (int i = 0; i <= (lim == 0 ? 9 : (subject.charAt(digits_number) - '0')); i++) {
			int n_lim = 0;
			if ((subject.charAt(digits_number) - '0') == i && (lim == 1 || digits_number == 0)) {
				n_lim = 1;
			}
			int n_three = three;
			if (i == 3) {
				n_three = 1;
			}
			ans += dfs(digits_number + 1, (mod3 * 10 + i) % 3, (mod8 * 10 + i) % 8, n_lim, n_three);
			ans %= MOD;
		}
		return dp[digits_number][mod3][mod8][lim][three] = ans;
	}

	static long nl() {
		try {
			long num = 0;
			boolean minus = false;
			while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
				;
			if (num == '-') {
				num = 0;
				minus = true;
			} else {
				num -= '0';
			}

			while (true) {
				int b = is.read();
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}

	static char nc() {
		try {
			int b = skip();
			if (b == -1)
				return 0;
			return (char) b;
		} catch (IOException e) {
		}
		return 0;
	}

	static double nd() {
		try {
			return Double.parseDouble(ns());
		} catch (Exception e) {
		}
		return 0;
	}

	static String ns() {
		try {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			if (b == -1)
				return "";
			sb.append((char) b);
			while (true) {
				b = is.read();
				if (b == -1)
					return sb.toString();
				if (b <= ' ')
					return sb.toString();
				sb.append((char) b);
			}
		} catch (IOException e) {
		}
		return "";
	}

	public static char[] ns(int n) {
		char[] buf = new char[n];
		try {
			int b = skip(), p = 0;
			if (b == -1)
				return null;
			buf[p++] = (char) b;
			while (p < n) {
				b = is.read();
				if (b == -1 || b <= ' ')
					break;
				buf[p++] = (char) b;
			}
			return Arrays.copyOf(buf, p);
		} catch (IOException e) {
		}
		return null;
	}

	public static byte[] nse(int n) {
		byte[] buf = new byte[n];
		try {
			int b = skip();
			if (b == -1)
				return null;
			is.read(buf);
			return buf;
		} catch (IOException e) {
		}
		return null;
	}

	static int skip() throws IOException {
		int b;
		while ((b = is.read()) != -1 && !(b >= 33 && b <= 126))
			;
		return b;
	}

	static boolean eof() {
		try {
			is.mark(1000);
			int b = skip();
			is.reset();
			return b == -1;
		} catch (IOException e) {
			return true;
		}
	}

	static int ni() {
		try {
			int num = 0;
			boolean minus = false;
			while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
				;
			if (num == '-') {
				num = 0;
				minus = true;
			} else {
				num -= '0';
			}

			while (true) {
				int b = is.read();
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}

	int[][][][][] dp = new int[10100][3][8][2][2];
}
0