library

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

View the Project on GitHub Harui-i/library

:x: test/verify/atcoder-tdpc-s.test.cpp

Depends on

Code

#define IGNORE
#define PROBLEM "https://atcoder.jp/contests/dp/tasks/dp_s"

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

using mint = modint1000000007;

struct dpState {
  int cmp_state; // -1: less than K, 0: equal to K, 1: greater than K
  int digsum_remainder; // digit sum % D

  dpState(int _cmp_state, int _digsum_remainder) : cmp_state(_cmp_state), digsum_remainder(_digsum_remainder) {}

  bool operator<(const dpState& other) const {
    return make_pair(cmp_state, digsum_remainder) < make_pair(other.cmp_state, other.digsum_remainder);
  }
};

// K以下の、桁和がDの倍数の数のみを受理するオートマトン
class Automaton : public Dfa<char, dpState> { 
  const vector<char> K_vec;
  const int D; 
  
public:
  using State = dpState;

  Automaton (const vector<char> _K_vec, int _d) : K_vec(_K_vec), D(_d) {}

  State init() const override {
    return State(0, 0);
  }

  State next(State s, char c, int i) const {
    State ret = s;
    if (s.cmp_state == 0) {
      if (c > K_vec[i]) ret.cmp_state = 1;
      if (c < K_vec[i]) ret.cmp_state = -1;
    }

    ret.digsum_remainder += c - '0';
    ret.digsum_remainder %= D;

    return ret;
  }

  bool accept(State s) const override {
    return s.cmp_state != 1 && s.digsum_remainder % D == 0;
  }

  bool unsuccessful(State s) const override {
    return s.cmp_state == 1;
  }

  bool successful([[maybe_unused]] State s) const override {
    return false;
  }

};

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  string K_str; cin >> K_str;
  vector<char> K_vec(K_str.begin(), K_str.end());

  int D; cin >> D; 
  
  Automaton atm(K_vec, D);

  vector<char> alphabet = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

  int Ksize = K_vec.size();
  map<dpState, mint> dp1, dp2; 
  mint ans = 0;

  dp1[atm.init()] = 1;

  for(int i=0; i<Ksize; i++) {
    for (char c : alphabet) {
      for (pair<dpState, mint> st_cnt : dp1) {
        dpState state = st_cnt.first;
        mint cnt = st_cnt.second;        

        dpState newState = atm.next(state, c, i);
        if (atm.unsuccessful(newState)) continue;

        dp2[newState] += cnt;
      }
    }

    swap(dp1,dp2);
    dp2.clear();
  }


  for (pair<dpState, mint> st_cnt: dp1) {
    if (atm.accept(st_cnt.first)) {
      ans += st_cnt.second;
    }
  }
  ans -= 1;// 0をカウントしてしまっているが、ゼロは正整数ではないので答えから1引く
  cout << ans.val() << endl; 
  return 0;
}
#line 1 "test/verify/atcoder-tdpc-s.test.cpp"
#define IGNORE
#define PROBLEM "https://atcoder.jp/contests/dp/tasks/dp_s"

#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"

template<int MOD>
struct static_modint {
    int value;

    constexpr explicit 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 = static_modint(1);
        while (exp > 0) {
            if (exp & 1) res *= base;
            base *= base;
            exp >>= 1;
        }
        return res;
    }

    constexpr static_modint inv() const {
        //return pow(MOD - 2);
        int g,x,y;
        tie(g,x,y) = extendedGCD(value, MOD);
        assert(g==1);
        if (x < 0) {
            x += MOD;
        }
        //cerr << g << " " << x << " " << y << " " << value << endl;
        //assert((((long)x*value)%MOD + MOD)%MOD == 1);
        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();
    }

    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 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 7 "test/verify/atcoder-tdpc-s.test.cpp"
#include <vector>
#include <map>

using mint = modint1000000007;

struct dpState {
  int cmp_state; // -1: less than K, 0: equal to K, 1: greater than K
  int digsum_remainder; // digit sum % D

  dpState(int _cmp_state, int _digsum_remainder) : cmp_state(_cmp_state), digsum_remainder(_digsum_remainder) {}

  bool operator<(const dpState& other) const {
    return make_pair(cmp_state, digsum_remainder) < make_pair(other.cmp_state, other.digsum_remainder);
  }
};

// K以下の、桁和がDの倍数の数のみを受理するオートマトン
class Automaton : public Dfa<char, dpState> { 
  const vector<char> K_vec;
  const int D; 
  
public:
  using State = dpState;

  Automaton (const vector<char> _K_vec, int _d) : K_vec(_K_vec), D(_d) {}

  State init() const override {
    return State(0, 0);
  }

  State next(State s, char c, int i) const {
    State ret = s;
    if (s.cmp_state == 0) {
      if (c > K_vec[i]) ret.cmp_state = 1;
      if (c < K_vec[i]) ret.cmp_state = -1;
    }

    ret.digsum_remainder += c - '0';
    ret.digsum_remainder %= D;

    return ret;
  }

  bool accept(State s) const override {
    return s.cmp_state != 1 && s.digsum_remainder % D == 0;
  }

  bool unsuccessful(State s) const override {
    return s.cmp_state == 1;
  }

  bool successful([[maybe_unused]] State s) const override {
    return false;
  }

};

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  string K_str; cin >> K_str;
  vector<char> K_vec(K_str.begin(), K_str.end());

  int D; cin >> D; 
  
  Automaton atm(K_vec, D);

  vector<char> alphabet = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

  int Ksize = K_vec.size();
  map<dpState, mint> dp1, dp2; 
  mint ans = 0;

  dp1[atm.init()] = 1;

  for(int i=0; i<Ksize; i++) {
    for (char c : alphabet) {
      for (pair<dpState, mint> st_cnt : dp1) {
        dpState state = st_cnt.first;
        mint cnt = st_cnt.second;        

        dpState newState = atm.next(state, c, i);
        if (atm.unsuccessful(newState)) continue;

        dp2[newState] += cnt;
      }
    }

    swap(dp1,dp2);
    dp2.clear();
  }


  for (pair<dpState, mint> st_cnt: dp1) {
    if (atm.accept(st_cnt.first)) {
      ans += st_cnt.second;
    }
  }
  ans -= 1;// 0をカウントしてしまっているが、ゼロは正整数ではないので答えから1引く
  cout << ans.val() << endl; 
  return 0;
}
Back to top page