結果

問題 No.1269 I hate Fibonacci Number
コンテスト
ユーザー Nachia
提出日時 2020-10-23 23:56:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 178 ms / 3,000 ms
コード長 1,935 bytes
コンパイル時間 2,014 ms
コンパイル使用メモリ 182,376 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 13:57:06
合計ジャッジ時間 3,523 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

const ULL M = 1000000007;

ULL F[88];
vector<string> S;

struct Node {
    int to[10];
    int z = 0;
    bool enable = false;
    Node() { rep(i, 10) to[i] = -1; }
};

vector<Node> V;

int main() {
    F[0] = F[1] = 1;
    for (int i = 2; i < 88; i++) F[i] = F[i - 1] + F[i - 2];

    ULL N, L, R; cin >> N >> L >> R;
    rep(i, 88) if (L <= F[i] && F[i] <= R) S.push_back(to_string(F[i]));

    V.push_back(Node());
    for (string& s : S) {
        int p = 0;
        for (char c : s) {
            int d = c - '0';
            if (V[p].to[d] == -1) {
                V[p].to[d] = V.size();
                V.push_back(Node());
            }
            p = V[p].to[d];
        }
        V[p].enable = true;
    }

    queue<int> Q;
    rep(t, 10) {
        if (V[0].to[t] == -1) V[0].to[t] = 0;
        else {
            V[V[0].to[t]].z = 0;
            Q.push(V[0].to[t]);
        }
    }
    while (Q.size()) {
        int q = Q.front(); Q.pop();
        rep(t, 10) {
            if (V[q].to[t] != -1) {
                Q.push(V[q].to[t]);
                int p = V[q].z;
                while (V[p].to[t] == -1) { p = V[p].z; }
                V[V[q].to[t]].enable = V[V[q].to[t]].enable || V[V[p].to[t]].enable;
                V[V[q].to[t]].z = V[p].to[t];
            }
        }
    }

    vector<ULL> dp(V.size());
    dp[0] = 1;

    rep(n, N) {
        vector<ULL> buf(V.size());
        rep(i, V.size()) rep(t, 10) {
            int p = i;
            while (V[p].to[t] == -1) p = V[p].z;
            buf[V[p].to[t]] += dp[i];
        }
        rep(i, V.size()) {
            dp[i] = buf[i] % M;
            if (V[i].enable) dp[i] = 0;
        }
    }

    ULL ans = 0;
    for (ULL a : dp) ans += a;
    ans += (M - 1);
    ans %= M;
    cout << ans << endl;

    return 0;
}
0