結果

問題 No.189 SUPER HAPPY DAY
ユーザー n_knuun_knuu
提出日時 2015-09-22 23:05:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 1,776 bytes
コンパイル時間 1,814 ms
コンパイル使用メモリ 146,896 KB
実行使用メモリ 12,196 KB
最終ジャッジ日時 2023-09-26 14:29:49
合計ジャッジ時間 2,982 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,416 KB
testcase_01 AC 3 ms
5,448 KB
testcase_02 AC 2 ms
5,412 KB
testcase_03 AC 2 ms
5,408 KB
testcase_04 AC 2 ms
5,540 KB
testcase_05 AC 2 ms
5,428 KB
testcase_06 AC 2 ms
5,684 KB
testcase_07 AC 3 ms
5,436 KB
testcase_08 AC 2 ms
5,408 KB
testcase_09 AC 3 ms
5,436 KB
testcase_10 AC 2 ms
5,612 KB
testcase_11 AC 2 ms
5,520 KB
testcase_12 AC 2 ms
5,412 KB
testcase_13 AC 7 ms
7,192 KB
testcase_14 AC 9 ms
8,056 KB
testcase_15 AC 9 ms
8,464 KB
testcase_16 AC 10 ms
9,072 KB
testcase_17 AC 10 ms
8,820 KB
testcase_18 AC 9 ms
8,192 KB
testcase_19 AC 11 ms
9,300 KB
testcase_20 AC 5 ms
6,432 KB
testcase_21 AC 5 ms
6,300 KB
testcase_22 AC 3 ms
5,536 KB
testcase_23 AC 10 ms
8,884 KB
testcase_24 AC 9 ms
8,848 KB
testcase_25 AC 17 ms
12,196 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(ll)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

ll dp1[210][2000][2], dp2[210][2000][2];
const ll mod = 1000000009;

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string M, D;
  cin >> M >> D;

  const ll L1 = M.size();
  dp1[0][0][0] = 1LL;
  REP(pos, L1) {
    REP(sum, 2000) {
      REP(cond, 2) {
	if (!dp1[pos][sum][cond]) continue;
	if (cond == 1) {
	  // no limit
	  REP(i, 10) {
	    dp1[pos+1][sum+i][1] += dp1[pos][sum][1];
	    dp1[pos+1][sum+i][1] %= mod;
	  }
	} else {
	  REP(i, M[pos]-'0') {
	    dp1[pos+1][sum+i][1] += dp1[pos][sum][0];
	    dp1[pos+1][sum+i][1] %= mod;
	  }
	  dp1[pos+1][sum+(M[pos]-'0')][0] += dp1[pos][sum][0];
	  dp1[pos+1][sum+(M[pos]-'0')][0] %= mod;
	}
      }
    }
  }

  const ll L2 = D.size();
  dp2[0][0][0] = 1LL;
  REP(pos, L2) {
    REP(sum, 2000) {
      REP(cond, 2) {
	if (!dp2[pos][sum][cond]) continue;
	if (cond == 1) {
	  // no limit
	  REP(i, 10) {
	    dp2[pos+1][sum+i][1] += dp2[pos][sum][1];
	    dp2[pos+1][sum+i][1] %= mod;
	  }
	} else {
	  REP(i, D[pos]-'0') {
	    dp2[pos+1][sum+i][1] += dp2[pos][sum][0];
	    dp2[pos+1][sum+i][1] %= mod;
	  }
	  dp2[pos+1][sum+(D[pos]-'0')][0] += dp2[pos][sum][0];
	  dp2[pos+1][sum+(D[pos]-'0')][0] %= mod;
	}
      }
    }
  }

  ll ret = 0;
  FOR(i, 1, 2000) {
    ret += (((dp1[L1][i][0] + dp1[L1][i][1]) % mod) * ((dp2[L2][i][0] + dp2[L2][i][1]) % mod)) % mod;
    ret %= mod;
  }
  cout << ret << endl;  
  return 0;
}
0