#705055 (C++14) No.1269 I hate Fibonacci Number

提出ソース

結果

問題	No.1269 I hate Fibonacci Number
ユーザー	ok
提出日時	2021-10-08 21:22:06
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	503 ms / 3,000 ms
コード長	4,778 bytes
コンパイル時間	1,220 ms
コンパイル使用メモリ	94,060 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-30 09:21:54
合計ジャッジ時間	5,261 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	6 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	137 ms 4,376 KB
testcase_14	AC	172 ms 4,376 KB
testcase_15	AC	18 ms 4,380 KB
testcase_16	AC	125 ms 4,380 KB
testcase_17	AC	4 ms 4,376 KB
testcase_18	AC	142 ms 4,376 KB
testcase_19	AC	98 ms 4,376 KB
testcase_20	AC	23 ms 4,380 KB
testcase_21	AC	81 ms 4,380 KB
testcase_22	AC	72 ms 4,380 KB
testcase_23	AC	80 ms 4,380 KB
testcase_24	AC	36 ms 4,380 KB
testcase_25	AC	48 ms 4,376 KB
testcase_26	AC	5 ms 4,380 KB
testcase_27	AC	2 ms 4,380 KB
testcase_28	AC	20 ms 4,376 KB
testcase_29	AC	44 ms 4,380 KB
testcase_30	AC	15 ms 4,376 KB
testcase_31	AC	220 ms 4,376 KB
testcase_32	AC	49 ms 4,380 KB
testcase_33	AC	503 ms 4,376 KB
testcase_34	AC	3 ms 4,376 KB
testcase_35	AC	11 ms 4,376 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,380 KB
testcase_38	AC	2 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<array>

using namespace std;

#define int long long
constexpr int MOD = 1000000007;

struct trie{
	int NUM_a;
	char A;
	trie** child;
	trie *fail;
	int val;
	int c;
	int d;
	
	trie() {
		NUM_a = 10;
		A = '0';
		val = 0;
		
		child = new trie*[NUM_a];
		for(int _ = 0; _ < NUM_a; _++) child[_] = NULL;
		
		c = 0;
		d = -1;
		fail = NULL;
	}
	
	~trie() {
		all_del();
		delete[] child;
	}
	
	void add(char *c){
		this->val++;
		if(*c == '\0') return;
		if(this->child[*c-A] == NULL){
			trie *node = new trie();
			this->child[*c-A] = node;
		}
		// else this->child[*c-A]->val++;
		
		
		this->child[*c-A]->add(c+1);
	}
	
	int find(char *c){
		if(*c == '\0'){
			int con = 0;
			for(int _ = 0; _ < NUM_a; _++){
				if(this->child[_] != NULL) con += this->child[_]->val;
			}
			return this->val - con;
		}
		
		if(this->child[*c-A] == NULL) return 0;
		else  return this->child[*c-A]->find(c+1);
	}
	
	void del(char *c){
		this->val--;
		if(*c == '\0') return ;
		
		if(this->child[*c-A] != NULL){
			this->child[*c-A]->del(c+1);
			if(child[*c-A]->val == 1) {
				delete child[*c-A];
				child[*c-A] = NULL;
			} 
		}
	}
	
	void all_del(){
		for(int _ = 0; _ < NUM_a; _++){
			if(this->child[_] != NULL) {
				child[_]->all_del();
				delete child[_];
				child[_] = NULL;
			}
		}
	}
	
	void print(int depth = 0){
		for(int _ = 0; _ < NUM_a; _++){
			if(child[_] != NULL){
				for(int __ = 0; __ < depth; __++) cout<<" ";
				cout<<(char)(A+_)<<" "<<child[_]->val<<" ";
				cout<<child[_]<<" "<<child[_]->fail<<" "<<child[_]->d;
				cout<<endl;
				this->child[_]->print(depth+1);
			}
		}
	}
};

struct Aho_Corasick {
	trie tr;
	vector<trie*> d;
	vector<string> S;
	
	void init(vector<string> &X){
		S = X;
		d.clear();
		queue<trie*> Q;
		
		for(string s : S){
			tr.add(&s[0]);
		}
		
		tr.d = d.size();
		d.push_back(&tr);
		
		for(int _ = 0; _ < tr.NUM_a; _++){
			if(tr.child[_] == NULL) continue;
			tr.child[_]->fail = &tr;
			Q.push(tr.child[_]);
		}
		
		while(!Q.empty()){
			trie *t = Q.front(); Q.pop();
			int con = 0;
			t->d = d.size();
			d.push_back(t);
			
			for(int _ = 0; _ < tr.NUM_a; _++){
				if(t->child[_] == NULL) continue;
				con += t->child[_]->val;
				
				trie *u = t->fail;
				
				while(u != &tr && u->child[_] == NULL) u = u->fail;
				
				if(u->child[_] == NULL) t->child[_]->fail = u;
				else t->child[_]->fail = u->child[_];
				
				Q.push(t->child[_]);
			}
			
			t->c = t->fail->c + t->val - con;
		}
		
		// tr.print();
	}
	
	int match(string &s){
		int res = 0;
		trie *t = &tr;
		
		for(char c : s){
			int C = c-t->A;
			
			while(true){
				if(t->child[C] != NULL){
					t = t->child[C];
					break;
				} else if(t == &tr) {
					break;
				} else {
					t = t->fail;
				}
			}
			res += t->c;
		}
		
		return res;
	}
	
	int match(string &s, vector<int> &con){
		int N = d.size();
		con = vector<int>(N);
		
		int res = 0;
		trie *t = &tr;
		
		for(char c : s){
			int C = c-t->A;
			
			while(true){
				if(t->child[C] != NULL){
					t = t->child[C];
					break;
				} else if(t == &tr) {
					break;
				} else {
					t = t->fail;
				}
			}
			
			res += t->c;
			con[t->d] += t->c;
		}
		
		return res;
	}
	
	int solve(int N){
		vector<int> dp(d.size());
		
		dp[0] = 1;
		
		for(int i = 0; i < N; i++){
			vector<vector<int>> ndp(d.size(), vector<int>(tr.NUM_a));
			vector<int> ndp2(d.size());
			
			for(int j = (int)d.size()-1; j >= 0; j--){
				for(int _ = 0; _ < tr.NUM_a; _++){
					if(d[j]->child[_] != NULL) {
						ndp[d[j]->child[_]->d][_] += dp[j] + ndp[j][_];
						ndp[j][_] = 0;
						ndp[d[j]->child[_]->d][_] %= MOD;
					} else if(d[j]->fail != NULL){
						ndp[d[j]->fail->d][_] += dp[j] + ndp[j][_];
						ndp[j][_] = 0;
						ndp[d[j]->fail->d][_] %= MOD;
					} else {
						ndp[j][_] += dp[j];
						ndp[j][_] %= MOD;
					}
				}
			}
			
			for(int j = (int)d.size()-1; j >= 0; j--){
				int con = 0, sum = 0;
				
				for(int _ = 0; _ < tr.NUM_a; _++){
					sum += ndp[j][_];
					sum %= MOD;
					if(d[j]->child[_] != NULL) {
						con += d[j]->child[_]->val;
					}
				}
				
				if(!d[j]->c) {
					ndp2[j] = sum;
				}
			}
			swap(dp, ndp2);
		}
		
		int res = 0;
		for(int i = 0; i < d.size(); i++){
			res += dp[i];
			res %= MOD;
		}
		
		res = (res + MOD - 1) % MOD;
		
		return res;
	}
};


signed main(){
	Aho_Corasick ac;
	vector<string> S;
	int N, L, R;
	vector<int> f;
	
	cin>>N>>L>>R;
	
	f.push_back(1);
	f.push_back(1);
	
	for(;f.back() <= R;){
		f.push_back(f[f.size()-1] + f[f.size()-2]);
	}
	for(int i = 0; i < f.size(); i++){
		if(L <= f[i] && f[i] <= R) {
			S.push_back(to_string(f[i]));
		}
	}
	
	ac.init(S);
	
	cout<<ac.solve(N)<<endl;
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード