結果
問題 | No.189 SUPER HAPPY DAY |
ユーザー |
![]() |
提出日時 | 2015-04-22 00:22:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,454 bytes |
コンパイル時間 | 1,528 ms |
コンパイル使用メモリ | 160,260 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-07-04 20:15:41 |
合計ジャッジ時間 | 2,252 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define MAX 999999 #define mod 1000000009 long long dp[205][2005][2]; long long dp2[205][2005][2]; long long dpans[2005]; long long dp2ans[2005]; int main() { string M, D; cin >> M >> D; long now = 0; dp[0][0][0] = 1; for (int i = 0; i < M.size(); i++) { int num = M[(int)M.size() - 1 - i] - '0'; for (int j = 0; j < 2000; j++) { for (int l = 0; l < 2; l++) { if (dp[i][j][l] == 0) continue; dp[i][j][l] %= mod; for (int k = 0; k < 10; k++) { if (k < num) dp[i + 1][(j + k)][0] += dp[i][j][l]; else if (k>num)dp[i + 1][(j + k)][1] += dp[i][j][l]; else dp[i + 1][(j + k)][l] += dp[i][j][l]; } } } } dp2[0][0][0] = 1; for (int i = 0; i < D.size(); i++) { int num = D[(int)D.size() - 1 - i] - '0'; for (int j = 0; j < 2000; j++) { for (int l = 0; l < 2; l++) { if (dp2[i][j][l] == 0) continue; dp2[i][j][l] %= mod; for (int k = 0; k < 10; k++) { if (k < num) dp2[i + 1][(j + k)][0] += dp2[i][j][l]; else if (k > num)dp2[i + 1][(j + k)][1] += dp2[i][j][l]; else dp2[i + 1][(j + k)][l] += dp2[i][j][l]; } } } } for (int i = 0; i < 2000; i++) { dpans[i] = dp[M.size()][i][0] % mod; dp2ans[i] = dp2[D.size()][i][0] % mod; } long long ans = 0; for (int i = 0; i < 2000; i++) { ans += dpans[i] * dp2ans[i]; ans %= mod; } ans += (mod - 1); ans %= mod; cout << ans << endl; }