結果

問題 No.1269 I hate Fibonacci Number
ユーザー 👑 NachiaNachia
提出日時 2020-11-10 00:01:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 38 ms / 3,000 ms
コード長 2,347 bytes
コンパイル時間 2,163 ms
コンパイル使用メモリ 184,624 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 17:03:17
合計ジャッジ時間 3,444 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 12 ms
5,376 KB
testcase_14 AC 15 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 12 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 12 ms
5,376 KB
testcase_19 AC 10 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 8 ms
5,376 KB
testcase_22 AC 7 ms
5,376 KB
testcase_23 AC 8 ms
5,376 KB
testcase_24 AC 5 ms
5,376 KB
testcase_25 AC 5 ms
5,376 KB
testcase_26 AC 3 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 6 ms
5,376 KB
testcase_30 AC 3 ms
5,376 KB
testcase_31 AC 19 ms
5,376 KB
testcase_32 AC 6 ms
5,376 KB
testcase_33 AC 38 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 3 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 # 

#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++)

static const int char_cnt = 10;

int char_to_idx(char c) { return c - '0'; }

struct AhoCorasick {
	struct Node {
		int to[char_cnt];
		int z = 0;
		int hit = -1;
		int suf = -1;
		Node() { rep(i, char_cnt) to[i] = -1; }
	};

	int N;
	vector<Node> V;

	struct SuffixRelation { int from, to; };
	vector<SuffixRelation> Suf;

	AhoCorasick(vector<string> T) {
		V.push_back(Node());
		N = T.size();

		rep(i, N) {
			int p = 0;
			for (char c : T[i]) {
				int d = char_to_idx(c);
				if (V[p].to[d] == -1) {
					V[p].to[d] = V.size();
					V.push_back(Node());
				}
				p = V[p].to[d];
			}
			if (V[p].hit != -1) Suf.push_back({ V[p].hit, i });
			else V[p].hit = i;
		}
		T.clear();

		queue<int> Q;
		rep(t, char_cnt) {
			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, char_cnt) {
				int p = V[q].z;
				while (V[p].to[t] == -1) { p = V[p].z; }
				if (V[q].to[t] == -1) V[q].to[t] = V[p].to[t];
				else {
					Q.push(V[q].to[t]);
					V[V[q].to[t]].z = V[p].to[t];
				}
			}
			V[q].suf = V[V[q].z].suf;
			if (V[q].hit != -1) {
				if (V[q].suf != -1) Suf.push_back({ V[q].hit, V[q].suf });
				V[q].suf = V[q].hit;
			}
		}
		reverse(Suf.begin(), Suf.end());
	}

	vector<int> search(const string& S) {
		vector<int> res(N);
		int p = 0;
		for (char c : S) {
			int d = char_to_idx(c);
			p = V[p].to[d];
			if (V[p].suf != -1) res[V[p].suf]++;
		}
		rep(i, Suf.size()) res[Suf[i].to] += res[Suf[i].from];
		return move(res);
	}
};


int main() {
	const ULL M = 1000000007;

	ULL F[88];
	vector<string> S;
	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]));

	auto V = move(AhoCorasick(S).V);
	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;
			buf[V[p].to[t]] += dp[i];
		}
		rep(i, V.size()) {
			dp[i] = buf[i] % M;
			if (V[i].suf != -1) dp[i] = 0;
		}
	}

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

	return 0;
}
0