結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
|
提出日時 | 2021-10-08 21:22:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 533 ms / 3,000 ms |
コード長 | 4,778 bytes |
コンパイル時間 | 1,441 ms |
コンパイル使用メモリ | 94,648 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-23 03:25:42 |
合計ジャッジ時間 | 4,890 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<iostream>#include<string>#include<vector>#include<algorithm>#include<utility>#include<queue>#include<array>using namespace std;#define int long longconstexpr 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;}