結果
問題 | No.372 It's automatic |
ユーザー |
|
提出日時 | 2024-05-29 17:44:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 982 ms / 6,000 ms |
コード長 | 5,932 bytes |
コンパイル時間 | 3,327 ms |
コンパイル使用メモリ | 251,736 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 21:04:31 |
合計ジャッジ時間 | 16,549 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#line 1 "yuki-372-itsautomatic.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/372"#line 1 "/home/samejima/CompetitiveProgramming/library/template/template.hpp"#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned int uint;template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}const int INTINF = 1000001000;const int INTMAX = 2147483647;const ll LLMAX = 9223372036854775807;const ll LLINF = 1000000000000000000;#line 1 "/home/samejima/CompetitiveProgramming/library/math/modint.hpp"template<int MOD>struct static_modint {int value;constexpr static_modint() : value(0) {}constexpr static_modint(long long v) {value = int(((v % MOD) + MOD) % MOD);}constexpr static_modint& operator+=(const static_modint& other) {if ((value += other.value) >= MOD) value -= MOD;return *this;}constexpr static_modint& operator-=(const static_modint& other) {if ((value -= other.value) < 0) value += MOD;return *this;}constexpr static_modint& operator*=(const static_modint& other) {value = int((long long)value * other.value % MOD);return *this;}constexpr static_modint operator+(const static_modint& other) const {return static_modint(*this) += other;}constexpr static_modint operator-(const static_modint& other) const {return static_modint(*this) -= other;}constexpr static_modint operator*(const static_modint& other) const {return static_modint(*this) *= other;}constexpr static_modint pow(long long exp) const {static_modint base = *this, res = 1;while (exp > 0) {if (exp & 1) res *= base;base *= base;exp >>= 1;}return res;}constexpr static_modint inv() const {return pow(MOD - 2);}constexpr static_modint& operator/=(const static_modint& other) {return *this *= other.inv();}constexpr static_modint operator/(const static_modint& other) const {return static_modint(*this) /= other;}constexpr bool operator!=(const static_modint& other) const {return val() != other.val();}constexpr bool operator==(const static_modint& other) const {return val() == other.val();}int val() const {return this->value;}friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) {return os << mi.value;}friend std::istream& operator>>(std::istream& is, static_modint& mi) {long long x;is >> x;mi = static_modint(x);return is;}};template <int mod>using modint = static_modint<mod>;using modint998244353 = modint<998244353>;using modint100000007 = modint<1000000007>;#line 1 "/home/samejima/CompetitiveProgramming/library/dp/automaton/automaton.hpp"// https://shino16.github.io/blog/post/algo/%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3/// Dfaインターフェースtemplate <typename Alphabet, typename State>class Dfa {public:virtual State init() const = 0; // 初期状態を返すvirtual State next([[maybe_unused]] State s, [[maybe_unused]] Alphabet a, [[maybe_unused]]int i) const = 0; //sにaを入力として与えた時の次の状態を返すvirtual bool accept([[maybe_unused]] State s) const = 0; // sをオートマトンが受理するかどうかvirtual bool successful([[maybe_unused]] State s) const { return false; } // どういうふうにnextしていこうが、絶対にacceptされる状態かどうかvirtual bool unsuccessful([[maybe_unused]] State s) const { return false; } // どういうふうにnextしていこうが、絶対にaccpetされない状態かどうか};#line 2 "/home/samejima/CompetitiveProgramming/library/dp/automaton/remainder.hpp"// nextは数字の右端に書き加えるイメージ。つまり、いろいろな桁数を考えられる。// しかし、固定した桁数に対して左から埋めていくパターンで使いたい場合もありそう。// 数字のMの倍数のみ受理するオートマトンtemplate <typename Alphabet>class RemainderAutomaton : public Dfa<Alphabet, int> {const int M;const int N_siz;public:using State = int;RemainderAutomaton(int _N_siz, int _M) : M(_M), N_siz(_N_siz) {}State init() const override {return State(0);}State next(State s, char c, int i) const override {State ret = ((long long)s*10 + (long long)(c - '0') )%M;return ret;}bool accept(State s) const override {return s == 0;}bool successful ([[maybe_unused]] State s) const override {return false;}bool unsuccessful([[maybe_unused]] State s) const override {return false;}};#line 6 "yuki-372-itsautomatic.test.cpp"using mint = modint100000007;int main() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);string S; cin >> S;vector<char> svec(S.begin(), S.end());int M; cin >> M;vector<char> alphabet = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };RemainderAutomaton<char> ra(S.size(), M);mint ans = 0;vector<mint>dp1(M), dp2(M);for (int i = 0; i < S.size(); i++) {if (S[i] == '0') ans += 1;else {dp2[(S[i] - '0') % M] += 1; // only one word substring, 'S[i]' .}for (int j = 0; j < M; j++) {dp2[j] += dp1[j]; // the case when S[i] is not chooseddp2[(j * 10 + S[i] - '0') % M] += dp1[j]; // the case when S[i] is choosen and added into past substrings}swap(dp1, dp2);dp2.assign(M, 0);}for(int i=0; i<M; i++) {if (ra.accept(i)) ans += dp1[i];}cout << ans.val() << endl;return 0;}