結果

問題 No.189 SUPER HAPPY DAY
ユーザー りおんりおん
提出日時 2020-04-04 20:35:49
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 3,512 bytes
コンパイル時間 2,002 ms
コンパイル使用メモリ 200,852 KB
実行使用メモリ 15,072 KB
最終ジャッジ日時 2023-09-16 06:09:43
合計ジャッジ時間 3,235 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
14,848 KB
testcase_01 AC 6 ms
14,892 KB
testcase_02 AC 6 ms
15,072 KB
testcase_03 AC 6 ms
14,788 KB
testcase_04 AC 6 ms
14,788 KB
testcase_05 AC 6 ms
14,848 KB
testcase_06 AC 7 ms
14,836 KB
testcase_07 AC 7 ms
14,900 KB
testcase_08 AC 6 ms
14,948 KB
testcase_09 AC 6 ms
14,988 KB
testcase_10 AC 7 ms
14,892 KB
testcase_11 AC 6 ms
14,788 KB
testcase_12 AC 6 ms
14,940 KB
testcase_13 AC 8 ms
14,888 KB
testcase_14 AC 8 ms
14,784 KB
testcase_15 AC 9 ms
15,072 KB
testcase_16 AC 9 ms
14,852 KB
testcase_17 AC 9 ms
14,936 KB
testcase_18 AC 8 ms
14,848 KB
testcase_19 AC 9 ms
14,868 KB
testcase_20 AC 7 ms
14,788 KB
testcase_21 AC 7 ms
14,904 KB
testcase_22 AC 7 ms
14,896 KB
testcase_23 AC 9 ms
14,884 KB
testcase_24 AC 10 ms
14,848 KB
testcase_25 AC 12 ms
14,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000009;
// const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) : x((x % mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint &operator+=(const mint a)
	{
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator-=(const mint a)
	{
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator*=(const mint a)
	{
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const
	{
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint &operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream &operator>>(istream &is, const mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

const int ILEN = 205;
const int JLEN = 1805;
const int KLEN = 2;
mint DPM[ILEN][JLEN][KLEN];
mint DPD[ILEN][JLEN][KLEN];
const int Match = 1;
const int Free = 0;

void DumpDP(mint dp[ILEN][JLEN][KLEN], int jmax, int slen){
	rep (j, jmax+1) {
		cout << j << ": ";
		rep(i, slen+1) {
			cout << dp[i][j][0] << "-" << dp[i][j][1] << " ";
		}
		cout << ": " << dp[slen][j][0] + dp[slen][j][1] << endl;
	}
	cout << endl;
}

void SolveKetaDP(mint dp[ILEN][JLEN][KLEN], string &s)
{
	dp[0][0][Match] = 1;

	// ※loopはいつも昇順にしたほうが良さそう
	// ※逆順にすると、遷移も逆方向にしないといけないので ※桁数を逆にする方が簡単
	rep (i, size(s)) {
		auto ni = i + 1;
		auto x = s[i] - '0';
		rep (j, JLEN) {
			rep (k, 2) {
				if (dp[i][j][k].x == 0) continue;

				rep (nx, 10) {
					auto nj = j + nx;
					auto nk = k; // ※nkは毎回初期化しないとおかしくなるよ！
					if (k == Match) {
						if (x < nx) continue;
						if (nx < x) {
							nk = Free;
						}
					} else {
					}

					dp[ni][nj][nk] += dp[i][j][k];
				}
			}
		}
	}
}

int main()
{
	string M, D;
	cin >> M >> D;
	// M = "2";
	// D = "3";

	// 2つの桁DPを解く

	// 桁DP
	// dp[桁（上位から）][合計][制限なし/あり] = パターン数
	SolveKetaDP(DPM, M);
	// DumpDP(DPM, 11, size(M));

	SolveKetaDP(DPD, D);
	// DumpDP(DPD, 11, size(D));

	// string filename = "test_my.txt";
	// ofstream f;
	// f.open(filename, ios::out);

	// 結果を計算
	// ※ 配るDPの場合、結果は S.Length(＝最後のi + 1) に格納されている
	// ※ 整数問題の場合、all 0
	// の分を1個マイナスするのを忘れずに！先行0にも要注意！ ※
	// MOD系は、最後のMODを忘れないことと、MODの前処理で負数にしないこと
	mint ans = 0;
	for (int j = 1; j < JLEN; j++){
		auto m = DPM[size(M)][j][0] + DPM[size(M)][j][1];
		auto d = DPD[size(D)][j][0] + DPD[size(D)][j][1];
		ans += m * d;

		// f << j << ": " << ans << ": " << m * d << endl;
	}			
	cout << ans << endl;
	return 0;
}
0