結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー ooaiu
提出日時 2025-08-17 18:01:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 5,000 ms
コード長 879 bytes
コンパイル時間 3,101 ms
コンパイル使用メモリ 286,216 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-17 18:01:12
合計ジャッジ時間 4,709 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::static_modint<9+(int)1e9>;
using ll = long long;
vector<vector<mint>> solve(const string& S) {
	int N = S.size();
	vector dp(N + 1, vector(2, vector<mint>(200*9+1)));
	dp[0][0][0] = 1;
	for(int i = 0; i < N; i++) {
		for(int less = 0; less < 2; less++) {
			for(int dc = 0; dc < 200*9+1; dc++) {
				int lim = less ? 9 : S[i] - '0';
				for(int d = 0; d <= lim; d++) if(dc+d<200*9+1){
					dp[i + 1][less|(d<S[i]-'0')][dc+d] += dp[i][less][dc];
				}
			}
		}
	}
	return dp[N];
}
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	string M, D;
	cin >> M >> D;
	auto dp1 = solve(M);
	auto dp2 = solve(D);
	mint ans = 0;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int x=0;x< 200*9+1;x++) {
		ans+=dp1[i][x]*dp2[j][x];
	}
	ans--;
	cout <<ans.val() << "\n";
}
0