結果

問題 No.1269 I hate Fibonacci Number
ユーザー ok
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0