#703341 (C++17) No.1269 I hate Fibonacci Number

• 問題: No.1269 I hate Fibonacci Number
• ユーザー: Felerius
• 提出日時: 2021-09-27 23:03:10
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE
• 実行時間: -
• コード長: 15,699 bytes
• コンパイル時間: 2,775 ms
• コンパイル使用メモリ: 244,988 KB
• 実行使用メモリ: 17,280 KB
• 最終ジャッジ日時: 2024-07-06 20:11:06
• 合計ジャッジ時間: 5,522 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,812 KB
testcase_01	AC	1 ms; 6,940 KB
testcase_02	AC	3 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	1 ms; 6,940 KB
testcase_07	AC	2 ms; 6,948 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	1 ms; 6,944 KB
testcase_10	AC	2 ms; 6,944 KB
testcase_11	AC	2 ms; 6,944 KB
testcase_12	AC	1 ms; 6,944 KB
testcase_13	AC	34 ms; 7,040 KB
testcase_14	AC	64 ms; 8,320 KB
testcase_15	AC	9 ms; 6,940 KB
testcase_16	AC	53 ms; 6,940 KB
testcase_17	AC	3 ms; 6,944 KB
testcase_18	AC	57 ms; 7,296 KB
testcase_19	AC	41 ms; 6,940 KB
testcase_20	AC	11 ms; 6,944 KB
testcase_21	AC	33 ms; 6,940 KB
testcase_22	AC	30 ms; 6,940 KB
testcase_23	AC	33 ms; 6,940 KB
testcase_24	AC	15 ms; 6,944 KB
testcase_25	AC	21 ms; 6,944 KB
testcase_26	AC	3 ms; 6,944 KB
testcase_27	RE	-
testcase_28	AC	8 ms; 6,944 KB
testcase_29	AC	21 ms; 6,944 KB
testcase_30	AC	8 ms; 6,944 KB
testcase_31	AC	80 ms; 9,600 KB
testcase_32	AC	22 ms; 6,944 KB
testcase_33	AC	141 ms; 17,280 KB
testcase_34	RE	-
testcase_35	AC	8 ms; 6,944 KB
testcase_36	AC	2 ms; 6,944 KB
testcase_37	AC	1 ms; 6,944 KB
testcase_38	AC	2 ms; 6,944 KB

ソースコード

#pragma GCC optimize("fast-math")
// begin "cp-lib/prelude.hpp"
#include <bits/stdc++.h>
#ifdef LOCAL
#  include <dbg.h>
#else
#  define dbg(...) do {} while (0)
#endif

#define cp_lib_4th(_1, _2, _3, x, ...)  x
#define cp_lib_rep(i, l, r)             for (int i = (l); (i) < (r); ++(i))
#define cp_lib_rep0(i, r)               cp_lib_rep(i, 0, r)
#define rep(...)                        cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__)
#define cp_lib_repr(i, r, l, ...)       for (int i = (r); (i) >= (l); --(i))
#define repr(...)                       cp_lib_repr(__VA_ARGS__, 0)
#define all(a)                          ::begin(a),::end(a)
#define trav(a, b)                      for (auto&& a : (b))

using namespace std;
using ll = long long;
using ld = long double;
[[maybe_unused]] static constexpr int INF = int(1e9 + 5);
[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;
template <class C> int sz(const C& c) { return int(::size(c)); }
// end "cp-lib/prelude.hpp"
// begin "cp-lib/io.hpp"
// begin "_assert.hpp"
#ifdef CP_LIB_DEBUG
#define cp_lib_assert(expr) \
    do { if (!(expr)) { \
        ::cerr << "assertion failed: " << #expr << " (" << __FILE__ << ':' << __LINE__ << ")\n"; \
        ::abort(); \
    } } while (0)
#else
#define cp_lib_assert(expr)
#endif
// end "_assert.hpp"
// begin "modint/_detect.hpp"
namespace cp_lib_modint { struct ModIntTag {}; }
// end "modint/_detect.hpp"
#include <unistd.h>

namespace cp_lib_io {
    constexpr int BUF_SIZE = 1 << 20;
    array<char, BUF_SIZE> ibuf, obuf;
    char *iptr = data(ibuf), *iend = iptr, *optr = data(obuf);

    template <class T, class = void> struct is_tuple_like : false_type {};
    template <class T> struct is_tuple_like<T, void_t<tuple_element_t<0, T>>> : true_type {};
    template <class T> struct is_std_array : false_type {};
    template <class T, size_t I> struct is_std_array<array<T, I>> : true_type {};

    void flush() { write(STDOUT_FILENO, begin(obuf), optr - begin(obuf)); optr = begin(obuf); }
    void ensure_write(int l) { if (end(obuf) - optr < l) flush(); }
    int _flush_atexit = []{ atexit(flush); return 0; }();
    void refill() {
        memmove(begin(ibuf), iptr, iend - iptr);
        iend -= iptr - begin(ibuf);
        iptr = begin(ibuf);
        iend += read(STDIN_FILENO, iend, end(ibuf) - iend);
    }
    void skip_ensure_read(int l) {
        do {
            while (iptr != iend && *iptr <= ' ') ++iptr;
            if (iend - iptr < l) refill();
        } while (*iptr <= ' ');
    }

    template <class T, class T2 = remove_reference_t<remove_cv_t<T>>>
    void print(T&& val) {
        if constexpr (is_same_v<T2, char>)
            ensure_write(2), *optr++ = val;
        else if constexpr (is_integral_v<T2> && !is_same_v<T2, bool>) {
            ensure_write(numeric_limits<T>::digits10 + 1 + is_signed_v<T2>);
            if (val < 0) { *optr++ = '-'; print(make_unsigned_t<T2>(-make_unsigned_t<T2>(val))); return; }
            array<char, 128> tmp;
            char* tptr = end(tmp);
            remove_const_t<T2> val_copy = val;
            do { *--tptr = char('0' + val_copy % 10), val_copy /= 10; } while (val_copy);
            memcpy(optr, tptr, end(tmp) - tptr);
            optr += end(tmp) - tptr;
#if __cpp_lib_to_chars >= 201611
        } else if constexpr (is_floating_point_v<T2>) {
            ensure_write(64);
            auto res = to_chars(optr, end(obuf), val, chars_format::fixed, 30);
            cp_lib_assert(res.ec == errc());
            optr = res.ptr;
#endif
        } else if constexpr (is_convertible_v<T, string_view>) {
            string_view sv(val);
            if (sz(sv) + 1 <= end(obuf) - optr)
                memcpy(optr, data(sv), sz(sv)), optr += sz(sv);
            else
                flush(), write(STDOUT_FILENO, data(sv), sz(sv));
        } else {
            if constexpr (is_same_v<T2, bool> || is_same_v<T2, vector<bool>::reference>)
                print(int(val));
            else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T2>)
                print(decltype(T2::mod())(val));
            else if constexpr (is_tuple_like<T2>() && !is_std_array<T2>())
                apply([](auto&&... items) { (print(items), ...); }, forward<T>(val));
            else
                trav(item, val) print(item);
            return;
        }
        *optr++ = ' ';
    }

    template <class T>
    void read(T& val) {
        if constexpr (is_same_v<T, char>)
            skip_ensure_read(1), val = *iptr++;
        else if constexpr (is_same_v<T, bool> || is_same_v<T, vector<bool>::reference>) {
            uint8_t ival; read(ival), val = bool(ival);
        } else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T>) {
            ll ival; read(ival); val = T(ival);
        } else if constexpr (is_integral_v<T>) {
            skip_ensure_read(numeric_limits<T>::digits10 + 1 + is_signed_v<T>);
            if (is_signed_v<T> && *iptr == '-') {
                ++iptr;
                make_unsigned_t<T> uval;
                read(uval);
                val = T(-uval);
            } else {
                val = 0;
                while (iptr != iend && *iptr > ' ') val = T(10 * val + (*iptr++ - '0'));
            }
#if __cpp_lib_to_chars >= 201611
        } else if constexpr (is_floating_point_v<T>) {
            skip_ensure_read(128);
            auto res = from_chars(iptr, iend, val);
            assert(res.ec == errc());
            iptr = const_cast<char*>(res.ptr);
#endif
        } else if constexpr (is_same_v<T, string>) {
            val = string();
            skip_ensure_read(1);
            do {
                auto* after = iptr;
                while (after != iend && *after > ' ') ++after;
                copy(iptr, after, back_inserter(val));
                if ((iptr = after) == iend)
                    refill();
                else
                    break;
            } while (iptr != iend);
        } else if constexpr (is_tuple_like<T>() && !is_std_array<T>())
            apply([](auto&... items) { (read(items), ...); }, val);
        else
            trav(item, val) read(item);
    }
}

using cp_lib_io::flush;

template <class... Args>
void print(Args&&... args) { (cp_lib_io::print(forward<Args>(args)), ...); }

template <class... Args>
void println(Args&&... args) {
    if (sizeof...(Args) > 0)
        (cp_lib_io::print(forward<Args>(args)), ...), *(cp_lib_io::optr - 1) = '\n';
    else
        cp_lib_io::ensure_write(1), *cp_lib_io::optr++ = '\n';
}

template <class... Args>
void printlns(Args&&... args) {
    ((cp_lib_io::print(forward<Args>(args)), *(cp_lib_io::optr - 1) = '\n'), ...);
}

template <class... Args>
void read(Args&... args) { (cp_lib_io::read(args), ...); }
// end "cp-lib/io.hpp"
// begin "cp-lib/modint/static-montgomery.hpp"
// begin "_base.hpp"
// begin "../math/ext-gcd.hpp"
template <class I>
constexpr enable_if_t<is_signed_v<I>, array<I, 3>> ext_gcd(I a, I b) {
    I x(1), y(0), x1(0), y1(1);
    while (b) {
        I t = a / b;
        tie(x, x1) = pair(x1, x - t * x1);
        tie(y, y1) = pair(y1, y - t * y1);
        tie(a, b) = pair(b, a - t * b);
    }
    return {a, x, y};
}
// end "../math/ext-gcd.hpp"

namespace cp_lib_modint {
    template <class Self, class Int>
    struct Base : ModIntTag {
        static_assert(is_same_v<Int, uint32_t> || is_same_v<Int, uint64_t>);

        friend constexpr Self operator+(Self l, Self r) { return l += r; }
        friend constexpr Self operator-(Self l, Self r) { return l -= r; }
        friend constexpr Self operator*(Self l, Self r) { return l *= r; }
        friend constexpr Self operator/(Self l, Self r) { return l * r.inv(); }
        friend constexpr Self& operator/=(Self& l, Self r) { return l *= r.inv(); }
        friend constexpr Self operator+(Self x) { return x; }
        friend constexpr Self operator-(Self x) { return Self(0) - x; }
        friend constexpr Self& operator++(Self& x) { return x += Self(1); }
        friend constexpr Self& operator--(Self& x) { return x -= Self(1); }
        friend constexpr Self operator++(Self& x, int) { auto y = x; ++x; return y; }
        friend constexpr Self operator--(Self& x, int) { auto y = x; --x; return y; }

#define CP_LIB_DEF(op) \
        template <class T, enable_if_t<is_integral_v<T>, int> = 0> \
        friend constexpr auto operator op(T l, Self r) { return Self(l) op r; }
        CP_LIB_DEF(==) CP_LIB_DEF(!=) CP_LIB_DEF(<) CP_LIB_DEF(+) CP_LIB_DEF(-) CP_LIB_DEF(*) CP_LIB_DEF(/)
#undef CP_LIB_DEF

        template <class T>
        constexpr enable_if_t<is_integral_v<T>, Self> pow(T e) const {
            Self r(1), b(*(Self*)(this));
            for (; e; b *= b, e >>= 1)
                if (e & 1) r *= b;
            return r;
        }

        constexpr optional<Self> try_inv() const {
            if (Self::is_prime())
                return *(Self*)this == Self() ? nullopt : optional(pow(Self::mod() - 2));
            auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod()));
            return (abs(g) == 1 ? optional(Self(x)) : nullopt);
        }
        constexpr Self inv() const {
            if (Self::is_prime()) return pow(Self::mod() - 2);
            auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod()));
            cp_lib_assert(abs(g) == 1);
            return x;
        }

        friend ostream& operator<<(ostream& out, Self m) { return out << uint64_t(m); }
        friend istream& operator>>(istream& in, Self& m) { ll x; in >> x; m = x; return in; }

     protected:
        Int i = 0;
    };

    template <class Int> using Wide = conditional_t<is_same_v<uint64_t, Int>, unsigned __int128, uint64_t>;
}
struct ModIntRaw {};
// end "_base.hpp"

namespace cp_lib_modint {
    template <class Int, Int Mod, bool IsPrime>
    class StaticMontgomery : public Base<StaticMontgomery<Int, Mod, IsPrime>, Int> {
        static_assert(Mod % 2 && Mod < (1ull << (sizeof(Int) * 8 - 2)));
        static constexpr Int INV = []{
            Int inv = Mod;
            rep(_, __builtin_ctz(sizeof(Int) * 8) - 1) inv *= 2 - Mod * inv;
            return inv;
        }();
        static constexpr Int R2 = Int(-Wide<Int>(Mod) % Mod);
        static constexpr Int reduce(Wide<Int> x) {
            return Int((x - Int(x) * INV * Wide<Int>(Mod))>> (sizeof(Int) * 8)) + Mod;
        }
        constexpr Int norm(Int x) const { return x >= Mod ? x - Mod : x; }

     public:
        static constexpr Int mod() { return Mod; }
        static constexpr bool is_prime() { return IsPrime; }

        StaticMontgomery() = default;
        template <class T, enable_if_t<is_unsigned_v<T>, int> = 0>
        constexpr StaticMontgomery(T x) { this->i = reduce(Wide<Int>(uint64_t(x) % Mod) * R2); }
        template <class T, enable_if_t<is_signed_v<T>, int> = 0>
        constexpr StaticMontgomery(T x) { this->i = reduce(Wide<Int>(ll(x) % ll(Mod) + ll(Mod)) * R2); }
        constexpr StaticMontgomery(Int x, ModIntRaw) { this->i = x; }

        template <class T, enable_if_t<is_integral_v<T>, int> = 0>
        constexpr explicit operator T() const { return T(norm(reduce(this->i))); }

        constexpr bool operator==(StaticMontgomery r) const { return norm(this->i) == norm(r.i); }
        constexpr bool operator!=(StaticMontgomery r) const { return norm(this->i) != norm(r.i); }
        constexpr bool operator<(StaticMontgomery r) const { return norm(this->i) < norm(r.i); }

        constexpr StaticMontgomery& operator+=(StaticMontgomery r) {
            if ((this->i += r.i) >= 2 * Mod)
                this->i -= 2 * Mod;
            return *this;
        }
        constexpr StaticMontgomery& operator-=(StaticMontgomery r) {
            if (make_signed_t<Int>(this->i -= r.i) < 0)
                this->i += 2 * Mod;
            return *this;
        }
        constexpr StaticMontgomery& operator*=(StaticMontgomery r) {
            return *this = {reduce(Wide<Int>(this->i) * r.i), {}};
        }
    };
}
template <uint32_t Mod, bool IsPrime> using StaticMontgomeryInt = cp_lib_modint::StaticMontgomery<uint32_t, Mod, IsPrime>;
template <uint64_t Mod, bool IsPrime> using StaticMontgomeryInt64 = cp_lib_modint::StaticMontgomery<uint64_t, Mod, IsPrime>;
// end "cp-lib/modint/static-montgomery.hpp"

template <int K>
struct Trie {
    static constexpr bool Sparse = (K == -1);
    vector<array<int, K>> t{1};
    vector<int> cnt = {INF};

    size_t size() const { return ::size(t); }
    int next(int v, int c) const { return t[v][c]; }

    template <class It, class ItEnd, class T = typename iterator_traits<It>::value_type>
    int add(It it, ItEnd it_end, T base = (is_same_v<T, char> ? 'a' : T(0))) {
        int v = 0;
        for (; it != it_end; ++it) {
            if (!t[v][*it - base])
                t[v][*it - base] = sz(t), t.emplace_back(), cnt.emplace_back();
            v = t[v][*it - base];
            ++cnt[v];
        }
        return v;
    }

    template <class It, class ItEnd, class T = typename iterator_traits<It>::value_type>
    void remove(It it, ItEnd it_end, T base = (is_same_v<T, char> ? 'a' : T(0))) {
        int v = 0;
        for (; it != it_end && --cnt[next(v, *it - base)]; v = next(v, *it++ - base))
            cp_lib_assert(next(v, *it - base));
        if (it != it_end)
            t[v][*it - base] = 0;
    }
};

template <int W>
class BitTrie : public Trie<2> {
    array<bool, W> bits;

    void to_bits(uint64_t x) { rep(i, W) bits[W - 1 - i] = (x >> i) & 1; }

    template <bool Max>
    uint64_t xor_eval(uint64_t x) const {
        uint64_t ans = 0;
        for (int i = W - 1, v = 0, bit = int((x >> i) & 1); i >= 0; bit = int((x >> --i) & 1)) {
            if (next(v, bit ^ Max))
                v = next(v, bit ^ Max), ans ^= (uint64_t(Max) << i);
            else
                v = next(v, !bit ^ Max), ans ^= (uint64_t(!Max) << i);
        }
        return ans;
    }

 public:
    uint64_t xor_min(uint64_t x) const { return xor_eval<false>(x); }
    uint64_t xor_max(uint64_t x) const { return xor_eval<true>(x); }

    int add(uint64_t x) { to_bits(x); return Trie<2>::add(all(bits)); }
    void remove(uint64_t x) { to_bits(x); Trie<2>::remove(all(bits)); }
};

template <int K = 26>
struct AhoCorasick : Trie<K> {
    template <class F>
    void build(F&& f) {
        queue<array<int, 4>> q;
        q.push({0, -1, 0, -1});
        while (sz(q)) {
            auto [v, c, p, plink] = q.front(); q.pop();
            int link = (p ? this->next(plink, c) : 0);
            rep(i, K) {
                if (this->next(v, i))
                    q.push({this->next(v, i), i, v, link});
                else
                    this->t[v][i] = (v ? this->next(link, i) : 0);
            }
            if (v)
                f(v, link, c, p);
        }
    }
};

int main() {
    int n; ll l, r; read(n, l, r);
    vector fib = {0ll, 1ll};
    while (fib.back() <= r)
        fib.push_back(fib.back() + fib[sz(fib) - 2]);

    AhoCorasick<10> ac;
    vector<bool> is_end;
    trav(fi, fib) {
        if (fi < l || r < fi)
            continue;
        auto s = to_string(fi);
        int v = ac.add(all(s), '0');
        if (v >= sz(is_end))
            is_end.resize(v + 1);
        is_end[v] = true;
    }
    ac.build([&](int v, int link, int, int) {
        is_end[v] = is_end[v] || is_end[link];
    });

    int m = sz(ac);
    using MI = StaticMontgomeryInt<int(1e9) + 7, true>;
    vector dp(n + 1, vector(m, MI(0)));
    dp[0][0] = 1;
    rep(i, n) rep(j, m) rep(k, 10)
        if (!is_end[j])
            dp[i + 1][ac.next(j, k)] += dp[i][j];

    MI ans = 0;
    rep(i, m)
        if (!is_end[i])
            ans += dp[n][i];
    println(ans - 1);
}