結果
問題 |
No.372 It's automatic
|
ユーザー |
![]() |
提出日時 | 2016-05-14 22:50:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,477 ms / 6,000 ms |
コード長 | 884 bytes |
コンパイル時間 | 1,744 ms |
コンパイル使用メモリ | 167,324 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 00:58:14 |
合計ジャッジ時間 | 32,537 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long dp[2][20001]; int nex[20001][10]; int M = 1000000007; int main(){ string s; cin >> s; int n = s.length(), m; cin >> m; int zero = -1; dp[0][0] = 1; for (int i = 0; i < m; ++i) { for (int j = 0; j < 10; ++j) { nex[i][j] = (i * 10 + j) % m; } } for (int i = 0, ii = 0; i < n; ++i, ii ^= 1) { int t = s[i] - '0'; int ij = ii ^ 1; for (int j = 0; j < m; j++) { dp[ij][j] += dp[ii][j]; dp[ij][nex[j][t]] += dp[ii][j]; } if (!t) { dp[ij][0] = (dp[ij][0] + M - 1) % M; ++zero; } for (int j = 0; j < m; ++j) { dp[ij][j] %= M; dp[ii][j] = 0; } } cout << (dp[n & 1][0] + zero + M) % M << "\n"; return 0; }