結果
問題 |
No.1085 桁和の桁和
|
ユーザー |
|
提出日時 | 2020-06-20 16:55:12 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 1,840 ms |
コンパイル使用メモリ | 160,756 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-11-06 17:42:51 |
合計ジャッジ時間 | 3,188 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i, n) for (ll i = 0; i < n; i++) #define REPR(i, n) for (ll i = n; i >= 0; i--) #define FOR(i, m, n) for (ll i = m; i < n; i++) #define FORR(i, m, n) for (ll i = m; i >= n; i--) #define REPO(i, n) for (ll i = 1; i <= n; i++) #define ll long long #define INF (ll)1 << 60 #define MINF (-1 * INF) #define ALL(n) n.begin(), n.end() #define MOD 1000000007 #define P pair<ll, ll> ll dp[110000][9], d; string s; int main() { cin >> s >> d; ll n = s.size(); dp[0][0] = 1; bool ok = true; REP(i, n){ if (s[i] != '0' and s[i] != '?') ok = false; if(s[i] == '?'){ REP(j, 9){ REP(k, 10){ dp[i + 1][(j + k) % 9] += dp[i][j]; dp[i + 1][(j + k) % 9] %= MOD; } } } else{ REP(j, 9){ dp[i + 1][(j + s[i] - '0') % 9] += dp[i][j]; dp[i + 1][(j + s[i] - '0') % 9] %= MOD; } } } if(d == 0){ cout << (ok ? 1 : 0) << endl; } else if(d == 9) cout << dp[n][0] - (ok ? 1 : 0)<<endl; else cout << dp[n][d] << endl; }