結果

問題 No.1269 I hate Fibonacci Number
コンテスト
ユーザー Mister
提出日時 2020-10-23 23:57:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 205 ms / 3,000 ms
コード長 3,499 bytes
コンパイル時間 1,107 ms
コンパイル使用メモリ 105,784 KB
最終ジャッジ日時 2025-01-15 14:25:41
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <functional>
#include <atcoder/modint>

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

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

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

    explicit PatternsMatching(T base) {
        nodes.emplace_back();
        enc = [=](T c) { return c - base; };
    }

    template <class Container>
    void add(const Container& s) {
        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].matched = true;
    }

    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;
                if (nodes[fpos].matched) nodes[npos].matched = true;

                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]; }
};

using lint = long long;
using mint = atcoder::modint1000000007;

void solve() {
    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));
            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.nodes[j].matched) continue;
                ndp[j] += dp[i];
            }
        }

        std::swap(dp, ndp);
    }

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

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

    solve();

    return 0;
}
0