結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー ゴリポン先生
提出日時 2026-01-17 15:36:49
言語 D
(dmd 2.111.0)
結果
RE  
実行時間 -
コード長 1,045 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,509 ms
コンパイル使用メモリ 203,060 KB
実行使用メモリ 8,336 KB
最終ジャッジ日時 2026-01-17 15:36:59
合計ジャッジ時間 7,482 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kmjp.hatenablog.jp/entry/2015/04/22/0900 より
// 桁DP
import std;

immutable MOD = 10L ^^ 9 + 9;
// 各桁の和がそれぞれ何通りあるかを数え上げる
long[int] enumDigitSum(char[] S)
{
	immutable mDig = 200;
	static long[mDig * 10 + 50][mDig + 5] dp;
	int total = 0;
	typeof(return) R;
	if (dp[0][0] == 0) {
		dp[0][0] = 1;
		foreach (i; 0 .. mDig + 2)
			foreach (y; 0 .. mDig * 10 + 2)
				foreach (x; 0 .. 10)
					(dp[i + 1][y + x] += dp[i][y]) %= MOD;
	}
	S.reverse;
	while (!S.empty) {
		int x = S[$ - 1] - '0';
		foreach (i; 0 .. x)
			foreach (y; 0 .. mDig * 10 + 2)
				if (dp[S.length - 1][y])
					(R[y + total + i] += dp[S.length - 1][y]) %= MOD;
		total += x;
		S.popBack;
	}
	R[total]++;
	return R;
}
void main()
{
	// 入力
	char[] M, D;
	readln.chomp.formattedRead("%s %s", M, D);
	// 答えの計算
	auto MM = enumDigitSum(M), DD = enumDigitSum(D);
	long ret = 0;
	foreach (e; MM.byKeyValue)
		if (e.key)
			ret += e.value * DD[e.key] % MOD;
	// 答えの出力
	writeln(ret % MOD);
}
0