This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#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; }