Verify/aho_corasick.test.cpp

• View this file on GitHub
• Last update: 2021-04-20 01:42:38+09:00
• Problem: https://yukicoder.me/problems/no/1269

Depends on

• Number/modint.hpp
• String/aho_corasick.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1269"

#include "../Number/modint.hpp"
#include "../String/aho_corasick.hpp"

#include <iostream>
#include <numeric>
#include <string>

using lint = long long;
using mint = ModInt<1000000007>;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int n;
    lint l, r;
    std::cin >> n >> l >> r;

    PatternsMatching<10, char> pm('0');
    {
        lint a = 1, b = 1;
        while (a <= r) {
            if (l <= a && a <= r)
                pm.add(std::to_string(a), 0);
            lint s = a + b;
            b = a;
            a = s;
        }
    }

    pm.build();
    int m = pm.nodes.size();

    std::vector<mint> dp(m, 0);
    dp[0] = 1;
    auto ndp = dp;

    while (n--) {
        std::fill(ndp.begin(), ndp.end(), 0);

        for (int i = 0; i < m; ++i) {
            for (int d = 0; d < 10; ++d) {
                int j = pm.next(i, d);
                if (!pm[j].ids.empty()) continue;
                ndp[j] += dp[i];
            }
        }

        std::swap(dp, ndp);
    }

    std::cout << std::accumulate(dp.begin(), dp.end(), mint(0)) - 1 << "\n";
}

#line 1 "Verify/aho_corasick.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1269"

#line 2 "Number/modint.hpp"

#include <iostream>

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }

    ModInt& operator++() { return *this += 1; }
    ModInt& operator--() { return *this -= 1; }

    // functions
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }
    ModInt inv() const {
        int s = val, t = MOD,
            xs = 1, xt = 0;

        while (t != 0) {
            auto div = s / t;

            s -= t * div;
            xs -= xt * div;

            std::swap(s, t);
            std::swap(xs, xt);
        }

        return xs;
    }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }

    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // comparator
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) {
        lint v;
        is >> v;
        x = v;
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) {
        return os << x.val;
    }
};

using modint1000000007 = ModInt<1000000007>;
using modint998244353 = ModInt<998244353>;
#line 2 "String/aho_corasick.hpp"

#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <functional>

template <int K, class T>
struct PatternsMatching {
    struct Node {
        std::array<int, K> nxt;
        int fail;
        std::vector<int> ids;

        explicit Node() : fail(0) { nxt.fill(-1); }
    };

    std::vector<Node> nodes;
    std::function<int(T)> enc;

    explicit PatternsMatching(T base)
        : nodes(1), enc([=](T c) { return c - base; }) {}

    template <class Container>
    void add(const Container& s, int id) {
        int pos = 0;
        for (T ci : s) {
            int c = enc(ci);

            int npos = nodes[pos].nxt[c];
            if (npos == -1) {
                npos = nodes.size();
                nodes[pos].nxt[c] = npos;
                nodes.emplace_back();
            }
            pos = npos;
        }
        nodes[pos].ids.push_back(id);
    }

    void build() {
        std::queue<int> que;
        for (int& pos : nodes[0].nxt) {
            if (pos == -1) {
                pos = 0;
            } else {
                que.push(pos);
            }
        }

        while (!que.empty()) {
            int pos = que.front();
            que.pop();

            for (int c = 0; c < K; ++c) {
                int npos = nodes[pos].nxt[c];
                if (npos == -1) continue;

                int p = nodes[pos].fail;
                while (nodes[p].nxt[c] == -1) p = nodes[p].fail;
                int fpos = next(nodes[pos].fail, c);

                nodes[npos].fail = fpos;
                std::copy(nodes[fpos].ids.begin(), nodes[fpos].ids.end(),
                          std::back_inserter(nodes[npos].ids));

                que.push(npos);
            }
        }
    }

    int next(int pos, int c) const {
        while (nodes[pos].nxt[c] == -1) pos = nodes[pos].fail;
        return nodes[pos].nxt[c];
    }

    // (id, end of matching)
    template <class Container>
    std::vector<std::pair<int, int>> matching(const Container& s) const {
        std::vector<std::pair<int, int>> ret;

        int pos = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            pos = next(pos, enc(s[i]));
            for (auto id : nodes[pos].ids) {
                ret.emplace_back(id, i + 1);
            }
        }

        return ret;
    }

    Node& operator[](int pos) { return nodes[pos]; }
    Node operator[](int pos) const { return nodes[pos]; }
};
#line 5 "Verify/aho_corasick.test.cpp"

#line 7 "Verify/aho_corasick.test.cpp"
#include <numeric>
#include <string>

using lint = long long;
using mint = ModInt<1000000007>;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int n;
    lint l, r;
    std::cin >> n >> l >> r;

    PatternsMatching<10, char> pm('0');
    {
        lint a = 1, b = 1;
        while (a <= r) {
            if (l <= a && a <= r)
                pm.add(std::to_string(a), 0);
            lint s = a + b;
            b = a;
            a = s;
        }
    }

    pm.build();
    int m = pm.nodes.size();

    std::vector<mint> dp(m, 0);
    dp[0] = 1;
    auto ndp = dp;

    while (n--) {
        std::fill(ndp.begin(), ndp.end(), 0);

        for (int i = 0; i < m; ++i) {
            for (int d = 0; d < 10; ++d) {
                int j = pm.next(i, d);
                if (!pm[j].ids.empty()) continue;
                ndp[j] += dp[i];
            }
        }

        std::swap(dp, ndp);
    }

    std::cout << std::accumulate(dp.begin(), dp.end(), mint(0)) - 1 << "\n";
}

Back to top page