library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Harui-i/library

:heavy_check_mark: test/verify/yuki-372-itsautomatic.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/372"

#include "template/template.hpp"
#include "math/modint.hpp"
#include "dp/automaton/remainder.hpp"
#include <vector>

using mint = modint1000000007;

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 < (int) 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 choosed

      dp2[(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;
}
#line 1 "test/verify/yuki-372-itsautomatic.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/372"

#line 1 "template/template.hpp"
#include <iostream>
#include <cassert>
using namespace std;
using ll = long long;
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 "math/modint.hpp"



#line 1 "math/external_gcd.hpp"



#include <tuple>

// g,x,y
template<typename T>
constexpr std::tuple<T, T, T> extendedGCD(T a, T b) {
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b != 0) {
        T q = a / b;
        T r = a % b;
        a = b;
        b = r;
        
        T xTemp = x0 - q * x1;
        x0 = x1;
        x1 = xTemp;
        
        T yTemp = y0 - q * y1;
        y0 = y1;
        y1 = yTemp;
    }
    return {a, x0, y0};
}

#line 5 "math/modint.hpp"
#include <type_traits>
#line 7 "math/modint.hpp"

template<int MOD, typename T = int>
struct static_modint {
    T value;

    constexpr explicit static_modint() : value(0) {}

    constexpr static_modint(long long v) {
        if constexpr (std::is_same<T, double>::value) {
            value = double(v);
        }
        else {
            value = int(((v % MOD) + MOD) % MOD);
        }
    }

    constexpr static_modint& operator+=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value += other.value;
        }
        else {
            if ((value += other.value) >= MOD) value -= MOD;
        }
        return *this;
    }

    constexpr static_modint& operator-=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value -= other.value;
        }
        else {
            if ((value -= other.value) < 0) value += MOD;
        }
        return *this;
    }

    constexpr static_modint& operator*=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value *= other.value;
        }
        else {
            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 = static_modint(1);
        while (exp > 0) {
            if (exp & 1) res *= base;
            base *= base;
            exp >>= 1;
        }
        return res;
    }

    constexpr static_modint inv() const {
        if constexpr (std::is_same<T, double>::value) {
            static_modint ret;
            ret.value = double(1.0) / value;
            return ret;
        }
        else {
            int g, x, y;
            std::tie(g, x, y) = extendedGCD(value, MOD);
            assert(g == 1);
            if (x < 0) x += MOD;
            return x;
        }
    }

    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();
    }

    T val() const {
        if constexpr (std::is_same<T, double>::value) {
            return double(value);
        }
        else 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 doublemodint = static_modint<59, double>;
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;


#line 1 "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 "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, [[maybe_unused]] 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 "test/verify/yuki-372-itsautomatic.test.cpp"
#include <vector>

using mint = modint1000000007;

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 < (int) 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 choosed

      dp2[(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;
}
Back to top page