test/yukicoder/1953.test.cpp

View this file on GitHub
Last update: 2022-11-06 09:10:22+09:00
Problem: https://yukicoder.me/problems/no/1953

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1953"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include "digitDP/ADFA/digit_dp_adfa.hpp"
#include "digitDP/ADFA/leq_adfa.hpp"

struct Monoid {
    ll val;
    ll leading_zero;
    ll num;
    bool undef = true;
    Monoid() { *this = zero(); }
    Monoid(ll val, ll leading_zero, ll num, bool undef = true) : val(val),
                                                leading_zero(leading_zero),
                                                num(num),
                                               undef(undef) {}
    static Monoid zero() { return Monoid(0,0,0); }
    static Monoid e() { return Monoid(0,1,0,false); }
    Monoid& operator+=(const Monoid &a) {
        if (this->undef) *this = a;
        else if (!a.undef) {
            this->val += a.val;
            this->leading_zero += a.leading_zero;
            this->num += a.num;
        }
        return *this;
    }
    Monoid& operator*=(int c) {
        if (c == 0) {
            this->val += this->num;
        }
        else {
            if (c == 4 || c == 6 || c == 9) {
                this->val += this->num+this->leading_zero;
            }
            else if (c == 8) {
                this->val += (this->num+this->leading_zero)*2;
            }
            this->num += this->leading_zero;
            this->leading_zero = 0;
        }
        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() {
    ll n;cin >> n;
    ll l = 0, r = 99193752409910740;
    while(r-l>1) {
        ll mid = (l+r)/2;
        if (n <= digitDP<Monoid>(LeqADFA(to_string(mid))).val) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    if (n == digitDP<Monoid>(LeqADFA(to_string(r))).val) {
        cout << r << endl;
    }
    else {
        puts("-1");
    }
    return 0;
}

#line 1 "test/yukicoder/1953.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1953"
#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 8 "test/yukicoder/1953.test.cpp"

struct Monoid {
    ll val;
    ll leading_zero;
    ll num;
    bool undef = true;
    Monoid() { *this = zero(); }
    Monoid(ll val, ll leading_zero, ll num, bool undef = true) : val(val),
                                                leading_zero(leading_zero),
                                                num(num),
                                               undef(undef) {}
    static Monoid zero() { return Monoid(0,0,0); }
    static Monoid e() { return Monoid(0,1,0,false); }
    Monoid& operator+=(const Monoid &a) {
        if (this->undef) *this = a;
        else if (!a.undef) {
            this->val += a.val;
            this->leading_zero += a.leading_zero;
            this->num += a.num;
        }
        return *this;
    }
    Monoid& operator*=(int c) {
        if (c == 0) {
            this->val += this->num;
        }
        else {
            if (c == 4 || c == 6 || c == 9) {
                this->val += this->num+this->leading_zero;
            }
            else if (c == 8) {
                this->val += (this->num+this->leading_zero)*2;
            }
            this->num += this->leading_zero;
            this->leading_zero = 0;
        }
        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() {
    ll n;cin >> n;
    ll l = 0, r = 99193752409910740;
    while(r-l>1) {
        ll mid = (l+r)/2;
        if (n <= digitDP<Monoid>(LeqADFA(to_string(mid))).val) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    if (n == digitDP<Monoid>(LeqADFA(to_string(r))).val) {
        cout << r << endl;
    }
    else {
        puts("-1");
    }
    return 0;
}