結果

問題 No.1269 I hate Fibonacci Number
ユーザー やむなくやむなく
提出日時 2020-10-23 23:54:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,179 bytes
コンパイル時間 2,205 ms
コンパイル使用メモリ 190,920 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-21 13:55:58
合計ジャッジ時間 3,725 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
5,376 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 2 ms
5,376 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 7 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
// Created by yamunaku on 2020/10/23.
//

#include <bits/stdc++.h>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

template<int char_size>
struct TrieNode {
    int nxt[char_size];

    int exist;
    ll count;
    bool flag;
    vector<int> accept;

    TrieNode() : exist(0), count(0), flag(false) {
        memset(nxt, -1, sizeof(nxt));
    }
};

template<int char_size, int margin>
struct Trie {
    using Node = TrieNode<char_size>;

    vector<Node> nodes;
    int root;

    Trie() : root(0) {
        nodes.push_back(Node());
    }

    void update_direct(int node, int id) {
        nodes[node].accept.push_back(id);
    }

    void update_child(int node, int child, int id) {
        ++nodes[node].exist;
    }

    void add(const string &str, int str_index, int node_index, int id) {
        if (str_index == str.size()) {
            update_direct(node_index, id);
            nodes[node_index].flag = true;
        } else {
            const int c = str[str_index] - margin;
            if (nodes[node_index].nxt[c] == -1) {
                nodes[node_index].nxt[c] = (int) nodes.size();
                nodes.push_back(Node());
            }
            add(str, str_index + 1, nodes[node_index].nxt[c], id);
            update_child(node_index, nodes[node_index].nxt[c], id);
        }
    }

    void add(const string &str, int id) {
        add(str, 0, 0, id);
    }

    void add(const string &str) {
        add(str, nodes[0].exist);
    }

    void query(const string &str, const function<void(int)> &f, int str_index, int node_index) {
        for (auto &idx : nodes[node_index].accept) f(idx);
        if (str_index == str.size()) {
            return;
        } else {
            const int c = str[str_index] - margin;
            if (nodes[node_index].nxt[c] == -1) return;
            query(str, f, str_index + 1, nodes[node_index].nxt[c]);
        }
    }

    void query(const string &str, const function<void(int)> &f) {
        query(str, f, 0, 0);
    }

    int count() const {
        return (nodes[0].exist);
    }

    int size() const {
        return ((int) nodes.size());
    }
};

template<int char_size, int margin>
struct AhoCorasick : Trie<char_size + 1, margin> {
    using Trie<char_size + 1, margin>::Trie;

    const int FAIL = char_size;
    vector<int> correct;

    void build(bool heavy = true) {
        correct.resize(this->size());
        for (int i = 0; i < this->size(); i++) {
            correct[i] = (int) this->nodes[i].accept.size();
        }
        queue<int> que;
        for (int i = 0; i <= char_size; i++) {
            if (~this->nodes[0].nxt[i]) {
                this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
                que.emplace(this->nodes[0].nxt[i]);
            } else {
                this->nodes[0].nxt[i] = 0;
            }
        }
        while (!que.empty()) {
            auto &now = this->nodes[que.front()];
            correct[que.front()] += correct[now.nxt[FAIL]];
            que.pop();
            for (int i = 0; i < char_size; i++) {
                if (now.nxt[i] == -1) continue;
                int fail = now.nxt[FAIL];
                while (this->nodes[fail].nxt[i] == -1) fail = this->nodes[fail].nxt[FAIL];
                this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
                if (heavy) {
                    auto &u = this->nodes[now.nxt[i]].accept;
                    auto &v = this->nodes[this->nodes[fail].nxt[i]].accept;
                    vector<int> accept;
                    set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));
                    u = accept;
                }
                que.emplace(now.nxt[i]);
            }

        }
    }

    map<int, int> match(const string &str, int now = 0) {
        map<int, int> result;
        for (auto &c : str) {
            while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL];
            now = this->nodes[now].nxt[c - margin];
            for (auto &v : this->nodes[now].accept) result[v] += 1;
        }
        return result;
    }

    pair<int, int> move(const char &c, int now) {
        int sum = 0;
        while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL];
        now = this->nodes[now].nxt[c - margin];
        sum += correct[now];
        return {sum, now};
    }

    void init() {
        this->nodes[this->root].count = 1;
    }

    mti nxxt;

    void buildnexxt() {
        int sz = this->nodes.size();
        nxxt = mti(sz, vi(10));
        rep(i, sz) {
            rep(j, 10) {
                nxxt[i][j] = this->nodes[i].nxt[j];
                if (nxxt[i][j] == -1) nxxt[i][j] = nxxt[this->nodes[i].nxt[FAIL]][j];
            }
        }
    }

    ll moveone() {
        int sz = this->nodes.size();
        vl tmp(sz, 0);
        rep(i, sz) {
            if (this->nodes[i].flag) continue;
            ll k = this->nodes[i].count;
            repl(j, 1, 10) {
                tmp[nxxt[i][j]] = (tmp[nxxt[i][j]] + k) % MOD;
            }
        }
        ll ans = 0;
        rep(i, sz) {
            if (this->nodes[i].flag) continue;
            ans = (ans + tmp[i]) % MOD;
            this->nodes[i].count = tmp[i];
        }
        return ans;
    }

    ll moveall() {
        int sz = this->nodes.size();
        vl tmp(sz, 0);
        rep(i, sz) {
            if (this->nodes[i].flag) continue;
            ll k = this->nodes[i].count;
            rep(j, 10) {
                tmp[nxxt[i][j]] = (tmp[nxxt[i][j]] + k) % MOD;
            }
        }
        ll ans = 0;
        rep(i, sz) {
            if (this->nodes[i].flag) continue;
            ans = (ans + tmp[i]) % MOD;
            this->nodes[i].count = tmp[i];
        }
        return ans;
    }

};

int main() {
    //CFS;
    int n;
    ll l, r;
    cin >> n >> l >> r;
    vl f(2, 1);
    while (f[f.size() - 2] < LINF - f[f.size() - 1]) {
        f.push_back(f[f.size() - 2] + f[f.size() - 1]);
    }
    AhoCorasick<10, '0'> ac;
    for (auto &x : f) {
//        cout << x << endl;
        if (l <= x && x <= r) {
            ac.add(to_string(x));
        }
    }
    ac.build();
    ac.buildnexxt();
    ac.init();
    ll ans = ac.moveone();
    repl(i, 1, n) ans = (ans + ac.moveall()) % MOD;
    cout << ans << endl;
    return 0;
}
0