This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kanpurin/digitDP
// "https://atcoder.jp/contests/dp/tasks/dp_s" #include <bits/stdc++.h> using namespace std; using ll = long long; #include "digitDP/ADFA/digit_dp_adfa.hpp" #include "digitDP/ADFA/leq_adfa.hpp" #include "digitDP/ADFA/intersection_adfa.hpp" #include "digitDP/sum_of_digits.hpp" #include "other/mint.hpp" constexpr int MOD = 1e9 + 7; struct Monoid { using T = mint<MOD>; T val; bool undef = true; Monoid() { *this = zero(); } Monoid(T val, bool undef = true) : val(val), undef(undef) {} // 単位元(和) static Monoid zero() { return Monoid(0); } static Monoid e() { return Monoid(1,false); } Monoid& operator+=(const Monoid &a) { if (this->undef) *this = a; else if (!a.undef) this->val += a.val; return *this; } Monoid& operator*=(int c) { return *this; } friend Monoid operator+(const Monoid& a, const Monoid& b) { return Monoid(a) += b; } friend Monoid operator*(const Monoid& a, int c) { return Monoid(a) *= c; } friend std::ostream& operator<<(std::ostream &os, const Monoid &x) { return os << x.val; } }; int main() { string k;cin >> k; int d;cin >> d; auto M1 = LeqADFA(k); auto M2 = SumOfDigitsAutomaton(d); auto M3 = IntersectionADFA(M1,M2); cout << digitDP<Monoid>(M3).val-1 << endl; return 0; }
#line 1 "test/atcoder/EDPC_S.cpp" // "https://atcoder.jp/contests/dp/tasks/dp_s" #include <bits/stdc++.h> using namespace std; using ll = long long; #line 3 "digitDP/automaton.hpp" struct Automaton { std::vector<std::vector<int>> delta; std::vector<bool> is_accept; int qsize; int init; int alphabet_size = 10; inline int next(int state, int c) const { return delta[state][c]; } inline bool accept(int state) const { return is_accept[state]; } inline int size() const {return qsize; } }; #line 4 "digitDP/ADFA/digit_dp_adfa.hpp" // ADFAが受理する文字列すべてについて求める template<typename Monoid> Monoid digitDP(const Automaton &adfa) { std::vector<int> indeg(adfa.size()); for (int i = 0; i < adfa.size(); i++) { for (int c = 0; c < adfa.alphabet_size; c++) { indeg[adfa.next(i,c)]++; } } std::vector<Monoid> dp(adfa.size()); dp[adfa.init] = Monoid::e(); Monoid ans; std::queue<int> que; que.push(adfa.init); while(!que.empty()) { int state = que.front(); que.pop(); for (int c = 0; c < adfa.alphabet_size; c++) { int next_s = adfa.next(state,c); dp[next_s] += dp[state]*c; indeg[next_s]--; if (indeg[next_s] == 0) que.push(next_s); } if (adfa.accept(state)) ans += dp[state]; } return ans; } #line 5 "digitDP/ADFA/leq_adfa.hpp" // 辞書順s以下の長さ|s|の文字列を受理 // ADFA struct LeqADFA : public Automaton { private: std::string str; bool eq; void initializer() { qsize = (str.size()+1)*2; init = 0; set_delta(); set_is_accept(); } void set_delta() { delta.resize(qsize,std::vector<int>(alphabet_size,0)); for (int i = 0; i < (int)str.size(); i++) { int state = i<<1; delta[state][str[i]-'0'] = state+2; for (int c = 0; c < str[i]-'0'; c++) { delta[state][c] = state+1; } for (int c = str[i]-'0'+1; c < alphabet_size; c++) { delta[state][c] = qsize-1; } for (int c = 0; c < alphabet_size; c++) { delta[state+1][c] = state+3; } } for (int c = 0; c < alphabet_size; c++) { delta[qsize-2][c] = qsize-1; delta[qsize-1][c] = qsize-1; } } void set_is_accept() { is_accept.resize(qsize,false); is_accept[qsize-2] = eq; is_accept[qsize-3] = true; } public: LeqADFA(std::string s, bool eq = true, int alpha_size = 10) : str(s), eq(eq) { assert(s.size() >= 1); alphabet_size = alpha_size; initializer(); } }; #line 6 "digitDP/ADFA/intersection_adfa.hpp" Automaton IntersectionADFA(const Automaton &adfa, const Automaton &dfa) { assert(adfa.alphabet_size == dfa.alphabet_size); Automaton M; M.alphabet_size = adfa.alphabet_size; unordered_map<ll,int> table; std::vector<int> x = {adfa.init}, y = {dfa.init}; table[x[0]*M.alphabet_size+y[0]] = 0; M.init = 0; for (int i = 0; i < x.size(); ++i) { M.delta.emplace_back(M.alphabet_size, -1); M.is_accept.emplace_back(adfa.accept(x[i]) && dfa.accept(y[i])); for (int c = 0; c < adfa.alphabet_size; c++) { int u = adfa.next(x[i],c), v = dfa.next(y[i],c); ll ps = (ll)u*M.alphabet_size+v; if (table.find(ps) == table.end()) { table[ps] = x.size(); x.emplace_back(u); y.emplace_back(v); } M.delta[i][c] = table[ps]; } } M.qsize = M.delta.size(); return M; } #line 3 "digitDP/sum_of_digits.hpp" // 桁和をdで割った余り struct SumOfDigitsAutomaton : public Automaton { private: int mod; void initializer() { qsize = mod; init = 0; set_delta(); set_is_accept(); } void set_delta() { delta.resize(qsize,std::vector<int>(alphabet_size)); for (int state = 0; state < qsize; state++) { for (int c = 0; c < alphabet_size; c++) { delta[state][c] = (state+c)%mod; } } } void set_is_accept() { is_accept.resize(qsize,false); is_accept[0] = true; } public: SumOfDigitsAutomaton(int mod, int alpha_size = 10) : mod(mod) { alphabet_size = alpha_size; initializer(); } }; #line 2 "other/mint.hpp" template< int MOD > struct mint { public: unsigned int x; mint() : x(0) {} mint(long long v) { long long w = (long long)(v % (long long)(MOD)); if (w < 0) w += MOD; x = (unsigned int)(w); } mint(std::string &s) { unsigned int z = 0; for (int i = 0; i < s.size(); i++) { z *= 10; z += s[i] - '0'; z %= MOD; } x = z; } mint operator+() const { return *this; } mint operator-() const { return mint() - *this; } mint& operator+=(const mint &a) { if ((x += a.x) >= MOD) x -= MOD; return *this; } mint& operator-=(const mint &a) { if ((x -= a.x) >= MOD) x += MOD; return *this; } mint& operator*=(const mint &a) { unsigned long long z = x; z *= a.x; x = (unsigned int)(z % MOD); return *this; } mint& operator/=(const mint &a) {return *this = *this * a.inv(); } friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint& lhs, const mint& rhs) { return lhs.x == rhs.x; } friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs.x != rhs.x; } friend std::ostream& operator<<(std::ostream &os, const mint &n) { return os << n.x; } friend std::istream &operator>>(std::istream &is, mint &n) { unsigned int x; is >> x; n = mint(x); return is; } mint inv() const { assert(x); return pow(MOD-2); } mint pow(long long n) const { assert(0 <= n); mint p = *this, r = 1; while (n) { if (n & 1) r *= p; p *= p; n >>= 1; } return r; } // 存在しない場合0を返す(二乗して確認). // O(log^2MOD) mint sqrt() const { if (this->x < 2) return *this; if (this->pow((MOD-1)>>1).x != 1) return mint(0); mint b = 1, one = 1; while (b.pow((MOD-1) >> 1) == 1) b += one; long long m = MOD-1, e = 0; while (m % 2 == 0) m >>= 1, e += 1; mint x = this->pow((m - 1) >> 1); mint y = (*this) * x * x; x *= (*this); mint z = b.pow(m); while (y.x != 1) { int j = 0; mint t = y; while (t != one) j += 1, t *= t; z = z.pow(1LL << (e-j-1)); x *= z; z *= z; y *= z; e = j; } return x; } }; #line 11 "test/atcoder/EDPC_S.cpp" constexpr int MOD = 1e9 + 7; struct Monoid { using T = mint<MOD>; T val; bool undef = true; Monoid() { *this = zero(); } Monoid(T val, bool undef = true) : val(val), undef(undef) {} // 単位元(和) static Monoid zero() { return Monoid(0); } static Monoid e() { return Monoid(1,false); } Monoid& operator+=(const Monoid &a) { if (this->undef) *this = a; else if (!a.undef) this->val += a.val; return *this; } Monoid& operator*=(int c) { return *this; } friend Monoid operator+(const Monoid& a, const Monoid& b) { return Monoid(a) += b; } friend Monoid operator*(const Monoid& a, int c) { return Monoid(a) *= c; } friend std::ostream& operator<<(std::ostream &os, const Monoid &x) { return os << x.val; } }; int main() { string k;cin >> k; int d;cin >> d; auto M1 = LeqADFA(k); auto M2 = SumOfDigitsAutomaton(d); auto M3 = IntersectionADFA(M1,M2); cout << digitDP<Monoid>(M3).val-1 << endl; return 0; }