結果
問題 | 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;}}}