結果

問題 No.260 世界のなんとか3
ユーザー 37zigen37zigen
提出日時 2016-08-25 23:39:57
言語 Java21
(openjdk 21)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,911 bytes
コンパイル時間 4,592 ms
コンパイル使用メモリ 93,180 KB
実行使用メモリ 93,112 KB
最終ジャッジ日時 2024-11-08 04:04:11
合計ジャッジ時間 19,690 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
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 MLE -
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 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 MLE -
testcase_28 MLE -
testcase_29 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package No200番台;

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

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;

	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) + is_sol(a) + MOD) % MOD;
		System.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) {
		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, s);
	}

	// Here, 1 is dealed as an identifier of TRUE。
	long dfs(int digits_number, int mod3, int mod8, int lim, int three, String s) {
		if (digits_number == s.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 : (s.charAt(digits_number) - '0')); i++) {
			int n_lim = 0;
			if ((s.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, s);
			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;
	}


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