結果

問題 No.1269 I hate Fibonacci Number
ユーザー chocorusk
提出日時 2020-10-25 21:56:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 21 ms / 3,000 ms
コード長 5,396 bytes
コンパイル時間 1,658 ms
コンパイル使用メモリ 141,832 KB
最終ジャッジ日時 2025-01-15 15:49:01
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
using ll=long long;
typedef pair<int, int> P;
template< int char_size >
struct TrieNode {
int nxt[char_size];
int exist;
vector< int > accept;
TrieNode() : exist(0) {
memset(nxt, -1, sizeof(nxt));
}
};
template< int char_size, int margin >
struct Trie {
using Node = TrieNode< char_size >;
vector< Node > nodes;
int root;
Trie() : root(0) {
nodes.push_back(Node());
}
void update_direct(int node, int id) {
nodes[node].accept.push_back(id);
}
void update_child(int node, int child, int id) {
++nodes[node].exist;
}
void add(const string &str, int str_index, int node_index, int id) {
if(str_index == str.size()) {
update_direct(node_index, id);
} else {
const int c = str[str_index] - margin;
if(nodes[node_index].nxt[c] == -1) {
nodes[node_index].nxt[c] = (int) nodes.size();
nodes.push_back(Node());
}
add(str, str_index + 1, nodes[node_index].nxt[c], id);
update_child(node_index, nodes[node_index].nxt[c], id);
}
}
void add(const string &str, int id) {
add(str, 0, 0, id);
}
void add(const string &str) {
add(str, nodes[0].exist);
}
void query(const string &str, const function< void(int) > &f, int str_index, int node_index) {
for(auto &idx : nodes[node_index].accept) f(idx);
if(str_index == str.size()) {
return;
} else {
const int c = str[str_index] - margin;
if(nodes[node_index].nxt[c] == -1) return;
query(str, f, str_index + 1, nodes[node_index].nxt[c]);
}
}
void query(const string &str, const function< void(int) > &f) {
query(str, f, 0, 0);
}
int count() const {
return (nodes[0].exist);
}
int size() const {
return ((int) nodes.size());
}
};
/**
* @brief Aho-Corasick()
* @docs docs/aho-corasick.md
*/
template< int char_size, int margin >
struct AhoCorasick : Trie< char_size + 1, margin > {
using Trie< char_size + 1, margin >::Trie;
const int FAIL = char_size;
vector< int > correct;
void build(bool heavy = true) {
correct.resize(this->size());
for(int i = 0; i < this->size(); i++) {
correct[i] = (int) this->nodes[i].accept.size();
}
queue< int > que;
for(int i = 0; i <= char_size; i++) {
if(~this->nodes[0].nxt[i]) {
this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
que.emplace(this->nodes[0].nxt[i]);
} else {
this->nodes[0].nxt[i] = 0;
}
}
while(!que.empty()) {
auto &now = this->nodes[que.front()];
int fail = now.nxt[FAIL];
correct[que.front()] += correct[fail];
que.pop();
for(int i = 0; i < char_size; i++) {
if(~now.nxt[i]) {
this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
if(heavy) {
auto &u = this->nodes[now.nxt[i]].accept;
auto &v = this->nodes[this->nodes[fail].nxt[i]].accept;
vector< int > accept;
set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));
u = accept;
}
que.emplace(now.nxt[i]);
} else {
now.nxt[i] = this->nodes[fail].nxt[i];
}
}
}
}
map< int, int > match(const string &str, int now = 0) {
map< int, int > result;
for(auto &c : str) {
now = this->nodes[now].nxt[c - margin];
for(auto &v : this->nodes[now].accept) result[v] += 1;
}
return result;
}
pair< int64_t, int > move(const char &c, int now = 0) {
now = this->nodes[now].nxt[c - margin];
return {correct[now], now};
}
pair< int64_t, int > move(const string &str, int now = 0) {
int64_t sum = 0;
for(auto &c : str) {
auto nxt = move(c, now);
sum += nxt.first;
now = nxt.second;
}
return {sum, now};
}
};
const ll MOD=1e9+7;
ll f[99];
int main()
{
int n; ll l, r; cin>>n>>l>>r;
f[0]=1, f[1]=1;
for(int i=2; i<90; i++){
f[i]=f[i-1]+f[i-2];
}
AhoCorasick<10, '0'> aho;
for(int i=1; i<90; i++){
if(l<=f[i] && f[i]<=r){
string s;
ll x=f[i];
while(x){
s+='0'+(x%10);
x/=10;
}
reverse(s.begin(), s.end());
aho.add(s);
}
}
aho.build();
int m=aho.nodes.size();
vector<ll> dp(m);
ll ans=MOD-1;
dp[0]=1;
for(int i=0; i<n; i++){
vector<ll> ndp(m);
for(int j=0; j<m; j++){
if(dp[j]==0) continue;
auto v=aho.nodes[j];
for(int k=0; k<10; k++){
int l=v.nxt[k];
if(!aho.nodes[l].accept.empty()) continue;
ndp[l]+=dp[j];
if(ndp[l]>=MOD) ndp[l]-=MOD;
}
}
swap(dp, ndp);
}
for(int i=0; i<m; i++){
(ans+=dp[i])%=MOD;
}
cout<<ans<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0