結果

問題 No.1269 I hate Fibonacci Number
ユーザー firiexpfiriexp
提出日時 2020-10-23 23:10:03
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,656 bytes
コンパイル時間 972 ms
コンパイル使用メモリ 99,612 KB
最終ジャッジ日時 2023-09-28 17:50:38
合計ジャッジ時間 1,564 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In instantiation of ‘struct AhoCorasick<10, 48>::Node’:
main.cpp:118:44:   required from here
main.cpp:23:23: エラー: ‘AhoCorasick<W, start>::Node::to’ has incomplete type
   23 |         array<int, W> to;
      |                       ^~
次のファイルから読み込み:  /usr/local/gcc7/include/c++/12.2.0/bits/stl_map.h:63,
         次から読み込み:  /usr/local/gcc7/include/c++/12.2.0/map:61,
         次から読み込み:  main.cpp:3:
/usr/local/gcc7/include/c++/12.2.0/tuple:1595:45: 備考: declaration of ‘struct std::array<int, 10>’
 1595 |   template<typename _Tp, size_t _Nm> struct array;
      |                                             ^~~~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

template<int W, int start>
class AhoCorasick {
public:
    struct Node {
        array<int, W> to;
        int fail;
        int val;
    };
    explicit AhoCorasick() : v(1) {}
    vector<Node> v;
    vector<int> ord;
    int add(string &s, int x = 0, int cur = 0){
        for (auto &&i : s) {
            if(!v[cur].to[i-start]) v[cur].to[i-start] = v.size(), v.emplace_back();
            cur = v[cur].to[i-start];
        }
        v[cur].val += x;
        return cur;
    }

    void build() {
        v[0].fail = -1;
        int l = 0, r = 1;
        ord.clear();
        ord.reserve(v.size());
        ord.emplace_back(0);
        while(l < r){
            int i = ord[l]; l++;
            for (int c = 0; c < W; ++c) {
                if(!v[i].to[c]) continue;
                int to = v[i].to[c];
                v[to].fail = (v[i].fail == -1 ? 0 : v[v[i].fail].to[c]);
                ord.emplace_back(to);
                r++;
            }
            if(i != 0){
                for (int c = 0; c < W; ++c) {
                    if(!v[i].to[c]) v[i].to[c] = v[v[i].fail].to[c];
                }
            }
        }
    }
    inline int next(int x, char c){ return v[x].to[c-start]; }
};

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }

template <u32 M>
struct modint {
    u32 val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v%(ll)(M)); if (x < 0) x += M; val = u32(x); }
    modint(bool v) { val = ((unsigned int)(v) % M); }
    modint& operator++() { val++; if (val == M) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = M; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= M) val -= M; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= M) val += M; return *this; }
    modint& operator*=(const modint& b) { u64 z = val; z *= b.val; val = (u32)(z % M); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(M-2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;

int main() {
    int n; ll l, r;
    cin >> n >> l >> r;
    vector<ll> v{1, 1};
    while(v.back() <= r) {
        ll val = v.end()[-1]+v.end()[-2];
        v.emplace_back(val);
    }
    AhoCorasick<10, '0'> aho;
    for (auto &&i : v) {
        string s = to_string(i);
        if(l <= i && i <= r) aho.add(s, 1);
    }

    aho.build();
    for (auto &&i : aho.ord) if(i) aho.v[i].val += aho.v[aho.v[i].fail].val;
    auto dp = make_v(n+1, aho.v.size(), mint(0));
    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < aho.v.size(); ++j) {
            for (int k = 0; k < 10; ++k) {
                int next = aho.next(j, '0'+k);
                if(!aho.v[next].val) dp[i+1][next] += dp[i][j];
            }
        }
    }
    cout << (accumulate(dp.back().begin(),dp.back().end(),mint(0))-1).val << "\n";
    return 0;
}
0