あまりを管理するオートマトン(remainder.hpp)
(dp/automaton/remainder.hpp)

• View this file on GitHub
• Last update: 2024-05-29 21:25:00+09:00
• Include: #include "dp/automaton/remainder.hpp"

これいるか？　nextは、数字の右側に桁を加えるような操作を考えている。 ‘998’に’2’を与えてnextすると’9982’に対応する状態が返ってくるイメージ。 わざわざライブラリにするほどのものでもなくね？？？ ライブラリにするほど複雑でもないから、1から書けばいいし、ライブラリにするなら「よく出るオートマトンは事前に書いておく」かつ「オートマトンのAND合成もライブラリにある」という状態が望ましいけど、 AND合成のオートマトンは書くの難しいし、どうせなら2つだけじゃなくて任意個の合成もできたほうが便利だけどそれもやっぱり難しいしで、オートマトンをライブラリにして有効に使うのは難しそう。

Depends on

• 決定性有限オートマトン(DFA, Deterministic Finite Automaton) (dp/automaton/automaton.hpp)

Verified with

• test/verify/yuki-372-itsautomatic.test.cpp

Code

#include "automaton.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 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;
  }
  
};

Back to top page