結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー ゴリポン先生
提出日時 2026-10-05 09:43:16
言語 D
(dmd 2.113.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
WA  
実行時間 -
コード長 2,403 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,386 ms
コンパイル使用メモリ 201,092 KB
実行使用メモリ 73,236 KB
最終ジャッジ日時 2026-10-05 09:43:36
合計ジャッジ時間 15,871 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/12/09/0900 より
// 数え上げ、剰余
import std;

immutable MOD = 10L ^^ 9 + 7;
long[] p10;
long[][][] memo;

// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}
long dfs(char[] S, int d, int m, int lead)
{
	int len = S.length.to!int;
	if (d >= len) return m == 0;
	if (memo[d][m][lead] >= 0) return memo[d][m][lead];
	long ret = 0;

	if (lead == 1) {
		foreach (i; 0 .. S[d] - '0') {
			if (i == 3) ret += p10[len - 1 - d];
			else ret += dfs(S, d + 1, (m + i) % 3, 0);
		}
		if (S[d] == '3') {
			long pat = 0;
			foreach (i; d + 1 .. len) pat = (pat * 10 + (S[i] - '0')) % MOD;
			ret += pat + 1;
		} else {
			ret += dfs(S, d + 1, (m + S[d] - '0') % 3, 1);
		}
	} else {
		foreach (i; 0 .. 10) {
			if (i == 3) ret += p10[len - 1 - d];
			else ret += dfs(S, d + 1, (m + i) % 3, 0);
		}
	}
	return memo[d][m][lead] = ret % MOD;
}
// 文字列で表された数を1減らす
void dec(ref char[] A)
{
	A.reverse;
	foreach (ref r; A) {
		if (r != '0') {
			r--;
			break;
		}
		r = '9';
	}
	if (A.length > 1 && A.back == '0') A.length -= 1;
	A.reverse;
}
int greed(int v, int p)
{
	int ret = 0;
	foreach (i; 1 .. v + 1) {
		if (i % p == 0) continue;
		int j = i;
		while (j) {
			if (j % 10 == 3) break;
			j /= 10;
		}
		if (j || (i % 3 == 0)) ret++;
	}
	return ret;
}
long calc(char[] S, long P)
{
	auto dp = new long[][](2, 3), t = new long[](2);
	if (S.length <= 5) return greed(S.to!int, P.to!int);

	long ret = 0;
	int low = S[$ - 5 .. $].to!int;
	S = S[0 .. $ - 5];
	foreach (j; 0 .. 2) {
		fill(memo, -1);
		foreach (i; 0 .. 3) dp[j][i] = dfs(S, 0, i, 1);
		foreach_reverse (r; S) t[j] = (t[j] * 10 + r - '0') % MOD;
		t[j]++;
		dec(S);
	}
	foreach (i; 0 .. 100_000) {
		int v = i;
		if (i % P == 0) continue;
		while (v) {
			if (v % 10 == 3) break;
			v /= 10;
		}
		if (v) ret += t[i > low];
		else ret += dp[i > low][i % 3];
	}
	return ret % MOD;
}

void main()
{
	// 入力
	char[] A, B;
	long P;
	readln.chomp.formattedRead("%s %s %d", A, B, P);
	// 答えの計算
	p10 = 1L.recurrence!((a,n) => a[n-1] * 10 % MOD).take(B.length + 1).array;
	memo = new long[][][](B.length + 1, 3, 2);
	dec(A);
	// 答えの出力
	writeln((calc(B, P) + MOD - calc(A, P)) % MOD);
}
0