結果

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

ソースコード

diff #
raw source code 

#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 = 62;

int char_to_idx(char c) {
	if ('0' <= c && c <= '9') return c - '0';
	if ('a' <= c && c <= 'z') return c - 'a' + 10;
	if ('A' <= c && c <= 'Z') return c - 'A' + 36;
	return -1;
}

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) {
				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]].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);
			while (V[p].to[d] == -1) p = V[p].z;
			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;
			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].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