結果

問題 No.189 SUPER HAPPY DAY
ユーザー wunderkammer2
提出日時 2020-02-12 13:35:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,867 bytes
コンパイル時間 957 ms
コンパイル使用メモリ 101,032 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-10-03 08:31:55
合計ジャッジ時間 2,267 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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