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/aoj-0570.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570"

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

using mint = modint<10000>;

class ZigZagDfa : public Dfa<int> {
  static constexpr int START = 30;
  static constexpr int NG = 31;

  int encode(int last_digit, int direction) const {
    return last_digit * 3 + direction;
  }

public:
  int state_count() const override {
    return 32;
  }

  int initial_state() const override {
    return START;
  }

  int next_state(int state, int digit) const override {
    if(state == NG) return NG;
    if(state == START) return encode(digit, 0);

    int last_digit = state / 3;
    int direction = state % 3;
    if(digit == last_digit) return NG;

    int next_direction = (last_digit < digit ? 1 : 2);
    if(direction != 0 && direction == next_direction) return NG;
    return encode(digit, next_direction);
  }

  bool accept(int state) const override {
    return state != START && state != NG;
  }
};

string decrement(string s) {
  int i = (int)s.size() - 1;
  while(i >= 0 && s[i] == '0') {
    s[i] = '9';
    i--;
  }
  if(i >= 0) s[i]--;

  int pos = 0;
  while(pos + 1 < (int)s.size() && s[pos] == '0') pos++;
  return s.substr(pos);
}

mint count_less_equal(const string& n, int m) {
  vector<int> alphabet = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  DfaPtr<int> less_equal = make_shared<DecimalLessEqualDfa>(n);
  DfaPtr<int> multiple_of_m = make_shared<LeadingZeroSkipDfa<int>>(
      make_shared<DecimalRemainderDfa>(m));
  DfaPtr<int> zig_zag = make_shared<LeadingZeroSkipDfa<int>>(
      make_shared<ZigZagDfa>());

  DfaPtr<int> condition = make_shared<AndDfa<int>>(multiple_of_m, zig_zag);
  DfaPtr<int> whole = make_shared<AndDfa<int>>(less_equal, condition);

  return count_fixed_length<mint>(*whole, alphabet, n.size());
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string A, B;
  int M;
  cin >> A >> B >> M;

  cout << count_less_equal(B, M) - count_less_equal(decrement(A), M) << '\n';
}
#line 1 "test/verify/aoj-0570.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570"

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

long long mod_pow_ll(long long x, long long n, long long mod) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = (__int128)ret * x % mod;
        x = (__int128)x * x % mod;
        n >>= 1;
    }
    return ret;
}

// x^2 = a (mod p) となる x を返す。存在しない場合は -1。
// p は素数であることを仮定する。
long long mod_sqrt(long long a, long long p) {
    a %= p;
    if (a < 0) a += p;
    if (a == 0) return 0;
    if (p == 2) return a;
    if (mod_pow_ll(a, (p - 1) / 2, p) != 1) return -1;
    if (p % 4 == 3) return mod_pow_ll(a, (p + 1) / 4, p);

    long long q = p - 1;
    int s = 0;
    while ((q & 1) == 0) {
        q >>= 1;
        s++;
    }

    long long z = 2;
    while (mod_pow_ll(z, (p - 1) / 2, p) != p - 1) z++;

    long long c = mod_pow_ll(z, q, p);
    long long x = mod_pow_ll(a, (q + 1) / 2, p);
    long long t = mod_pow_ll(a, q, p);
    int m = s;

    while (t != 1) {
        int i = 1;
        long long tt = (__int128)t * t % p;
        while (tt != 1) {
            tt = (__int128)tt * tt % p;
            i++;
        }
        long long b = c;
        for (int j = 0; j < m - i - 1; j++) b = (__int128)b * b % p;
        x = (__int128)x * b % p;
        c = (__int128)b * b % p;
        t = (__int128)t * c % p;
        m = i;
    }

    return x;
}

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

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

    static constexpr int mod() { return MOD; }

    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 {
        return static_modint(0) - *this;
    }

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

    long long sqrt_val() const {
        return mod_sqrt(value, MOD);
    }

    static_modint sqrt() const {
        long long ret = sqrt_val();
        assert(ret != -1);
        return static_modint(ret);
    }

    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"



#include <functional>
#include <memory>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

template <typename Alphabet = int>
struct Dfa {
  using alphabet_type = Alphabet;
  using state_type = int;

  virtual int state_count() const = 0;
  virtual int initial_state() const = 0;
  virtual int next_state(int state, Alphabet c) const = 0;
  virtual bool accept(int state) const = 0;
  virtual ~Dfa() = default;
};

template <typename Alphabet = int>
using DfaPtr = std::shared_ptr<Dfa<Alphabet>>;

template <typename Alphabet = int>
class ProductPolicyDfa : public Dfa<Alphabet> {
  std::vector<DfaPtr<Alphabet>> dfas;
  std::vector<int> base;
  int states;
  std::function<bool(const std::vector<bool>&)> policy;

public:
  ProductPolicyDfa(std::vector<DfaPtr<Alphabet>> dfas,
                   std::function<bool(const std::vector<bool>&)> policy)
      : dfas(std::move(dfas)), states(1), policy(std::move(policy)) {
    base.resize(this->dfas.size());
    for(int i = 0; i < (int)this->dfas.size(); i++) {
      base[i] = states;
      states *= this->dfas[i]->state_count();
    }
  }

  int encode(const std::vector<int>& component_states) const {
    int state = 0;
    for(int i = 0; i < (int)dfas.size(); i++) {
      state += component_states[i] * base[i];
    }
    return state;
  }

  std::vector<int> decode(int state) const {
    std::vector<int> component_states(dfas.size());
    for(int i = 0; i < (int)dfas.size(); i++) {
      component_states[i] = (state / base[i]) % dfas[i]->state_count();
    }
    return component_states;
  }

  int state_count() const override {
    return states;
  }

  int initial_state() const override {
    std::vector<int> component_states(dfas.size());
    for(int i = 0; i < (int)dfas.size(); i++) {
      component_states[i] = dfas[i]->initial_state();
    }
    return encode(component_states);
  }

  int next_state(int state, Alphabet c) const override {
    std::vector<int> component_states = decode(state);
    for(int i = 0; i < (int)dfas.size(); i++) {
      component_states[i] = dfas[i]->next_state(component_states[i], c);
    }
    return encode(component_states);
  }

  bool accept(int state) const override {
    std::vector<int> component_states = decode(state);
    std::vector<bool> accepted(dfas.size());
    for(int i = 0; i < (int)dfas.size(); i++) {
      accepted[i] = dfas[i]->accept(component_states[i]);
    }
    return policy(accepted);
  }
};

template <typename Alphabet = int>
class AndDfa : public Dfa<Alphabet> {
  DfaPtr<Alphabet> lhs;
  DfaPtr<Alphabet> rhs;
  int rhs_states;

public:
  AndDfa(DfaPtr<Alphabet> lhs, DfaPtr<Alphabet> rhs)
      : lhs(std::move(lhs)), rhs(std::move(rhs)), rhs_states(this->rhs->state_count()) {}

  int encode(int lhs_state, int rhs_state) const {
    return lhs_state * rhs_states + rhs_state;
  }

  std::pair<int, int> decode(int state) const {
    return {state / rhs_states, state % rhs_states};
  }

  int state_count() const override {
    return lhs->state_count() * rhs->state_count();
  }

  int initial_state() const override {
    return encode(lhs->initial_state(), rhs->initial_state());
  }

  int next_state(int state, Alphabet c) const override {
    auto [a, b] = decode(state);
    return encode(lhs->next_state(a, c), rhs->next_state(b, c));
  }

  bool accept(int state) const override {
    auto [a, b] = decode(state);
    return lhs->accept(a) && rhs->accept(b);
  }
};

template <typename T, typename Alphabet = int>
T count_fixed_length(const Dfa<Alphabet>& dfa, const std::vector<Alphabet>& alphabet, int length) {
  std::unordered_map<int, T> dp, next_dp;
  dp[dfa.initial_state()] = T(1);

  for(int i = 0; i < length; i++) {
    next_dp.clear();
    for(const auto& [state, value] : dp) {
      for(const Alphabet& c : alphabet) {
        next_dp[dfa.next_state(state, c)] += value;
      }
    }
    dp.swap(next_dp);
  }

  T answer = T(0);
  for(const auto& [state, value] : dp) {
    if(dfa.accept(state)) answer += value;
  }
  return answer;
}

class DecimalLessEqualDfa : public Dfa<int> {
  std::vector<int> digits;

public:
  explicit DecimalLessEqualDfa(const std::string& n) {
    digits.reserve(n.size());
    for(char c : n) digits.push_back(c - '0');
  }

  int encode(int pos, int rel) const {
    return pos * 3 + rel;
  }

  std::pair<int, int> decode(int state) const {
    return {state / 3, state % 3};
  }

  int state_count() const override {
    return ((int)digits.size() + 1) * 3;
  }

  int initial_state() const override {
    return encode(0, 0);
  }

  int next_state(int state, int digit) const override {
    auto [pos, rel] = decode(state);
    if(pos == (int)digits.size()) return encode(pos, 2);

    if(rel == 0) {
      if(digit < digits[pos]) rel = 1;
      if(digit > digits[pos]) rel = 2;
    }
    return encode(pos + 1, rel);
  }

  bool accept(int state) const override {
    auto [pos, rel] = decode(state);
    return pos == (int)digits.size() && rel != 2;
  }
};

template <typename Alphabet = int>
class LeadingZeroSkipDfa : public Dfa<Alphabet> {
  DfaPtr<Alphabet> inner;
  Alphabet zero;
  int inner_states;

public:
  LeadingZeroSkipDfa(DfaPtr<Alphabet> inner, Alphabet zero = Alphabet())
      : inner(std::move(inner)), zero(zero), inner_states(this->inner->state_count()) {}

  int encode(bool started, int inner_state) const {
    return (started ? inner_states : 0) + inner_state;
  }

  std::pair<bool, int> decode(int state) const {
    if(state < inner_states) return {false, state};
    return {true, state - inner_states};
  }

  int state_count() const override {
    return inner_states * 2;
  }

  int initial_state() const override {
    return encode(false, inner->initial_state());
  }

  int next_state(int state, Alphabet c) const override {
    auto [started, inner_state] = decode(state);
    if(!started && c == zero) return encode(false, inner_state);
    return encode(true, inner->next_state(inner_state, c));
  }

  bool accept(int state) const override {
    auto [started, inner_state] = decode(state);
    if(started) return inner->accept(inner_state);

    int zero_state = inner->next_state(inner->initial_state(), zero);
    return inner->accept(zero_state);
  }
};


#line 1 "dp/automaton/remainder.hpp"



#line 5 "dp/automaton/remainder.hpp"

class DecimalRemainderDfa : public Dfa<int> {
  int mod;

public:
  explicit DecimalRemainderDfa(int mod) : mod(mod) {}

  int state_count() const override {
    return mod;
  }

  int initial_state() const override {
    return 0;
  }

  int next_state(int state, int digit) const override {
    return ((long long)state * 10 + digit) % mod;
  }

  bool accept(int state) const override {
    return state == 0;
  }
};

using RemainderAutomaton = DecimalRemainderDfa;


#line 10 "test/verify/aoj-0570.test.cpp"

using mint = modint<10000>;

class ZigZagDfa : public Dfa<int> {
  static constexpr int START = 30;
  static constexpr int NG = 31;

  int encode(int last_digit, int direction) const {
    return last_digit * 3 + direction;
  }

public:
  int state_count() const override {
    return 32;
  }

  int initial_state() const override {
    return START;
  }

  int next_state(int state, int digit) const override {
    if(state == NG) return NG;
    if(state == START) return encode(digit, 0);

    int last_digit = state / 3;
    int direction = state % 3;
    if(digit == last_digit) return NG;

    int next_direction = (last_digit < digit ? 1 : 2);
    if(direction != 0 && direction == next_direction) return NG;
    return encode(digit, next_direction);
  }

  bool accept(int state) const override {
    return state != START && state != NG;
  }
};

string decrement(string s) {
  int i = (int)s.size() - 1;
  while(i >= 0 && s[i] == '0') {
    s[i] = '9';
    i--;
  }
  if(i >= 0) s[i]--;

  int pos = 0;
  while(pos + 1 < (int)s.size() && s[pos] == '0') pos++;
  return s.substr(pos);
}

mint count_less_equal(const string& n, int m) {
  vector<int> alphabet = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  DfaPtr<int> less_equal = make_shared<DecimalLessEqualDfa>(n);
  DfaPtr<int> multiple_of_m = make_shared<LeadingZeroSkipDfa<int>>(
      make_shared<DecimalRemainderDfa>(m));
  DfaPtr<int> zig_zag = make_shared<LeadingZeroSkipDfa<int>>(
      make_shared<ZigZagDfa>());

  DfaPtr<int> condition = make_shared<AndDfa<int>>(multiple_of_m, zig_zag);
  DfaPtr<int> whole = make_shared<AndDfa<int>>(less_equal, condition);

  return count_fixed_length<mint>(*whole, alphabet, n.size());
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string A, B;
  int M;
  cin >> A >> B >> M;

  cout << count_less_equal(B, M) - count_less_equal(decrement(A), M) << '\n';
}
Back to top page