結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー 37zigen
提出日時 2016-08-25 23:26:53
言語 Java
(openjdk 23)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,112 bytes
コンパイル時間 4,159 ms
コンパイル使用メモリ 79,396 KB
実行使用メモリ 83,464 KB
最終ジャッジ日時 2024-11-08 03:17:46
合計ジャッジ時間 22,118 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other MLE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

package No200番台;

import java.util.Scanner;

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

	long MOD = 1_000_000_000 + 7;

	void solver() {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		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;
	}

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