結果
問題 |
No.372 It's automatic
|
ユーザー |
![]() |
提出日時 | 2016-05-14 01:20:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 857 bytes |
コンパイル時間 | 1,692 ms |
コンパイル使用メモリ | 167,120 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 00:46:14 |
合計ジャッジ時間 | 32,589 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 WA * 1 |
ソースコード
#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, k; 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'; for (int j = 0; j < m; j++) { dp[ii ^ 1][j] += dp[ii][j]; dp[ii ^ 1][nex[j][t]] += dp[ii][j]; } if (!t) { dp[ii ^ 1][0] += M - 1; ++zero; } for (int j = 0; j < m; ++j) { dp[ii ^ 1][j] %= M; dp[ii][j] = 0; } } cout << (dp[n & 1][0] + zero) % M << "\n"; return 0; }