結果

問題 No.189 SUPER HAPPY DAY
ユーザー wunderkammer2wunderkammer2
提出日時 2020-02-12 13:35:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,867 bytes
コンパイル時間 918 ms
コンパイル使用メモリ 101,824 KB
実行使用メモリ 9,176 KB
最終ジャッジ日時 2024-04-14 11:34:16
合計ジャッジ時間 2,331 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,944 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 3 ms
6,944 KB
testcase_12 AC 3 ms
6,940 KB
testcase_13 AC 16 ms
7,000 KB
testcase_14 AC 21 ms
7,040 KB
testcase_15 AC 18 ms
8,256 KB
testcase_16 AC 19 ms
8,960 KB
testcase_17 AC 21 ms
8,576 KB
testcase_18 AC 18 ms
8,064 KB
testcase_19 AC 25 ms
7,936 KB
testcase_20 AC 11 ms
6,940 KB
testcase_21 AC 12 ms
6,940 KB
testcase_22 AC 4 ms
6,940 KB
testcase_23 AC 16 ms
8,960 KB
testcase_24 AC 16 ms
8,960 KB
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000009;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

const int SUM_MAX = 9 * 199;

vector<ll> calc(string N)
{
	//dp0[i][j] := 左からi桁目までを決めたとき、Nを超えないことが確定していて、かつ各桁の数字の合計値がjとなる数の個数
	//dp1[i][j] := 左からi桁目までを決めたとき、Nを超えないことが確定しておらず、かつ各桁の数字の合計値がjとなる数の個数
	//iは1始まり
	//jは最大 = 9*199（Nは最大200桁）
	vector<vector<ll>> dp0(N.size() + 1, vector<ll>(SUM_MAX + 1, 0));
	vector<vector<ll>> dp1(N.size() + 1, vector<ll>(SUM_MAX + 1, 0));

	dp1[0][0] = 1;

	rep(i, N.size())
	{
		int d = N[i] - '0';

		reple(j, 0, 9)
		{
			rep(k, SUM_MAX)
			{
				if (k + j > SUM_MAX) continue;

				dp0[i + 1][k + j] += dp0[i][k];
				dp0[i + 1][k + j] %= mod;

				if (j < d)
				{
					dp0[i + 1][k + j] += dp1[i][k];
					dp0[i + 1][k + j] %= mod;
				}
				else if (j == d)
				{
					dp1[i + 1][k + j] += dp1[i][k];
					dp1[i + 1][k + j] %= mod;
				}
			}
		}
	}

	vector<ll> dp(SUM_MAX + 1, 0);

	rep(i, SUM_MAX)
	{
		dp[i] += (dp0[N.size()][i] + dp1[N.size()][i]) % mod;
	}

	return dp;
}

int main()
{	
	string M, D;
	cin >> M >> D;

	vector<ll> dpM = calc(M);
	vector<ll> dpD = calc(D);

	ll count = 0;

	//合計は1以上
	repl(i, 1, SUM_MAX)
	{
		count += (dpM[i] * dpD[i]) % mod;
		count %= mod;
	}

	cout << count << endl;

	return 0;
}
0