55D - Beautiful numbers - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int S = 20786;
int trans[S][10];
bool isok[S];
namespace Automaton {
    using node = array<int, 2>;
    constexpr int N = 72578;
    int tot, trans[N][10];
    map<node, int> id;
    bool isok[N];
    int lcm(int a, int b) {
        if (!a || !b) {
            return a + b;
        }
        return a / __gcd(a, b) * b;
    }
    int dfs(node u) {
        int idu = id[u];
        if (!idu) {
            id[u] = ++tot;
            idu = tot;
            isok[tot] = u[0] ? u[1] % u[0] == 0 : 1;
        } else {
            return idu;
        }
        for (int i = 0; i <= 9; i++) {
            node v = u;
            v[0] = lcm(v[0], i);
            v[1] = (v[1] * 10 + i) % 2520;
            trans[idu][i] = dfs(v);
        }
        return idu;
    }
    vector<int> sta[N];
    int bel[N], cnt;
    void hopcroft() {
        cnt = 1;
        for (int i = 1; i <= tot; i++) {
            sta[isok[i]].push_back(i);
            bel[i] = isok[i];
        }
        while (1) {
            bool upd = 0;
            for (int i = 0; i <= cnt; i++) {
                for (int c = 0; c <= 9; c++) {
                    bool flag = 0;
                    for (int j : sta[i]) {
                        if (bel[trans[j][c]] != bel[trans[sta[i][0]][c]]) {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) continue;
                    upd = 1;
                    cnt++;
                    vector<int> A;
                    for (int j : sta[i]) {
                        if (bel[trans[j][c]] == bel[trans[sta[i][0]][c]]) {
                            A.push_back(j);
                        } else {
                            sta[cnt].push_back(j);
                            bel[j] = cnt;
                        }
                    }
                    swap(sta[i], A);
                }
            }
            if (!upd) {
                break;
            }
        }
    }
    void build() {
        dfs({});
        // cerr << "automaton size " << tot << "\n";
        hopcroft();
        // cerr << "minimized size " << cnt << "\n";
        // cerr << "start " << bel[id[{}]] << "\n";
        for (int i = 1; i <= tot; i++) {
            for (int j = 0; j <= 9; j++) {
                ::trans[bel[i]][j] = bel[trans[i][j]];
            }
            ::isok[bel[i]] = isok[i];
        }
    }
}
string a;
ll f[20][S][2];
ll dp(int i, int j, bool k) {
    if (i == -1) {
        return isok[j];
    }
    if (~f[i][j][k]) {
        return f[i][j][k];
    }
    ll ans = 0;
    int lim = k ? 9 : a[i] - '0';
    for (int c = 0; c <= lim; c++) {
        ans += dp(i - 1, trans[j][c], k | (c < a[i] - '0'));
    }
    return f[i][j][k] = ans;
}
ll calc(ll x) {
    a = to_string(x);
    reverse(a.begin(), a.end());
    memset(f, -1, sizeof f);
    return dp((int)a.size() - 1, 1, 0);
}
void solve() {
    ll l, r;
    cin >> l >> r;
    cout << calc(r) - calc(l - 1) << "\n";
}
bool check(string s) {
    int u = 1;
    for (char c : s) {
        u = trans[u][c - '0'];
    }
    return isok[u];
}
int main() {
    Automaton::build();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}