結果

問題 No.1269 I hate Fibonacci Number
ユーザー 👑 NachiaNachia
提出日時 2020-10-23 23:56:34
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 179 ms / 3,000 ms
コード長 1,935 bytes
コンパイル時間 1,832 ms
コンパイル使用メモリ 179,004 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-28 19:16:32
合計ジャッジ時間 4,034 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 26 ms
4,380 KB
testcase_14 AC 32 ms
4,380 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 26 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 27 ms
4,380 KB
testcase_19 AC 18 ms
4,380 KB
testcase_20 AC 6 ms
4,380 KB
testcase_21 AC 17 ms
4,380 KB
testcase_22 AC 14 ms
4,376 KB
testcase_23 AC 16 ms
4,376 KB
testcase_24 AC 8 ms
4,376 KB
testcase_25 AC 10 ms
4,376 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 6 ms
4,376 KB
testcase_29 AC 9 ms
4,376 KB
testcase_30 AC 4 ms
4,376 KB
testcase_31 AC 55 ms
4,376 KB
testcase_32 AC 11 ms
4,376 KB
testcase_33 AC 179 ms
4,376 KB
testcase_34 AC 2 ms
4,380 KB
testcase_35 AC 4 ms
4,376 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 2 ms
4,380 KB
testcase_38 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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