結果
問題 | No.372 It's automatic |
ユーザー |
![]() |
提出日時 | 2016-05-12 17:47:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,487 ms / 6,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 1,589 ms |
コンパイル使用メモリ | 166,708 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 00:34:44 |
合計ジャッジ時間 | 32,797 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--) #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int, int> P; const int mod7 = 1e9 + 7; const int MAX_M = 20010; string s; int M; // mod M の個数 // dp[i] = (mod M == i) である部分列の個数 int dp1[MAX_M]; int dp2[MAX_M]; // 添え字は mod M // 部分列の個数は mod 1e9 + 7 signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); cin >> s; cin >> M; int ans = 0; rep(i, s.size()) { // 他の部分列の末尾にs[i]をつける場合 rep(j, M) { (dp2[(j * 10 + (s[i] - '0')) % M] += dp1[j]) %= mod7; } // s[i]を先頭とする場合 if (s[i] != '0') { ++dp2[(s[i] - '0') % M] %= mod7; } else { ans++; // "0"はそのまま解になる } rep(i, M) dp1[i] = dp2[i]; } (ans += dp1[0]) % mod7; cout << ans << endl; }