結果
問題 | No.372 It's automatic |
ユーザー |
![]() |
提出日時 | 2016-05-13 23:19:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,254 bytes |
コンパイル時間 | 1,635 ms |
コンパイル使用メモリ | 172,388 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-05 17:42:01 |
合計ジャッジ時間 | 4,806 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 6 RE * 17 |
ソースコード
/*_ooOoo_o8888888o88" . "88(| -_- |)O\ = /O____/`---'\____.' \\| |// `./ \\||| : |||// \/ _||||| -:- |||||- \| | \\\ - /// | || \_| ''\---/'' | |\ .-\__ `-` ___/-. /___`. .' /--.--\ `. . __."" '< `.___\_<|>_/___.' >'"".| | : `- \`.;`\ _ /`;.`/ - ` : | |\ \ `-. \_ __\ /__ _/ .-` / /======`-.____`-.___\_____/___.-`____.-'======`=---='^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^pass System Test!*/#include <bits/stdc++.h>using namespace std;template <typename T>std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {if (!v.empty()) {out << '[';std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));out << "\b\b]";}return out;}template <typename T1, typename T2>std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {out << "[" << p.first << ", " << p.second << "]";return out;}template <class T, class U>void chmin(T &t, U f) {if (t > f) t = f;}template <class T, class U>void chmax(T &t, U f) {if (t < f) t = f;}template <typename T>void uniq(vector<T> &v) {v.erase(unique(v.begin(), v.end()), v.end());}const int MOD = 1e9 + 7;int main() {cin.tie(0);ios::sync_with_stdio(false);string inS;cin >> inS;int N = inS.size();vector<int> S(N);for (int i = 0; i < N; ++i) S[i] = inS[i] - '0';int M;cin >> M;vector<vector<int>> remainer(M, vector<int>(10, 0));for (int i = 0; i < M; ++i)for (int j = 0; j < 10; ++j) remainer[i][j] = (i + j) % M;vector<int> dp(M, 0);dp[0] = 1;int zeros = 0;for (int i = 0; i < N; ++i) {vector<int> next(N, 0);for (int m = 0; m < M; ++m) {next[m] += dp[m];next[m] %= MOD;int r = remainer[m][S[i]];next[r] += dp[m];if (m == 0 && S[i] == 0) {zeros++;next[r] = (next[r] - 1 + MOD) % MOD;} else {next[r] %= MOD;}}dp.swap(next);}cout << ((dp[0] + zeros - 1 + MOD) % MOD) << endl;}