結果
問題 | No.1085 桁和の桁和 |
ユーザー |
![]() |
提出日時 | 2020-06-19 22:20:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 118 ms / 2,000 ms |
コード長 | 1,064 bytes |
コンパイル時間 | 1,710 ms |
コンパイル使用メモリ | 171,652 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2024-11-06 17:37:27 |
合計ジャッジ時間 | 4,271 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long MOD = 1000000007; int main(){ string T; cin >> T; int D; cin >> D; int N = T.size(); bool zero = true; bool zero2 = true; for (int i = 0; i < N; i++){ if (T[i] != '0' && T[i] != '?'){ zero = false; } if (T[i] != '0'){ zero2 = false; } } if (D == 0){ if (zero){ cout << 1 << endl; } else { cout << 0 << endl; } } else { vector<vector<long long>> dp(N + 1, vector<long long>(9, 0)); dp[0][0] = 1; for (int i = 0; i < N; i++){ if (T[i] == '?'){ for (int j = 0; j < 9; j++){ for (int k = 0; k <= 9; k++){ dp[i + 1][(j + k) % 9] += dp[i][j]; dp[i + 1][(j + k) % 9] %= MOD; } } } else { int d = T[i] - '0'; for (int j = 0; j < 9; j++){ dp[i + 1][(j + d) % 9] = dp[i][j]; } } } if (D == 9 && zero){ cout << (dp[N][0] - 1 + MOD) % MOD << endl; } else { cout << dp[N][D % 9] << endl; } } }