結果

問題 No.1269 I hate Fibonacci Number
ユーザー tokusakurai
提出日時 2020-10-26 10:14:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 210 ms / 3,000 ms
コード長 4,622 bytes
コンパイル時間 2,484 ms
コンパイル使用メモリ 210,420 KB
最終ジャッジ日時 2025-01-15 15:51:04
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
//const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};
template<int char_size, char base>
struct Trie{
struct Node{
vector<int> next, accept;
int count; //
Node() : count(0){
next.assign(char_size, -1);
}
};
vector<Node> nodes;
Trie() {nodes.eb();}
int count() const {return nodes.front().count;}
int size() const {return sz(nodes);}
void insert(const string &s, int id){
int now = 0;
rep(i, sz(s)){
int &next = nodes[now].next[s[i]-base];
if(next == -1){
next = size(), nodes.eb();
}
nodes[now].count++, now = next;
}
nodes[now].count++, nodes[now].accept.pb(id);
}
void insert(const string &s) {insert(s, count());}
bool search(const string &s, bool prefix = false) const{
int now = 0;
rep(i, sz(s)){
now = nodes[now].next[s[i]-base];
if(now == -1) return false;
}
return (prefix)? true : !nodes[now].accept.empty();
}
};
template<int char_size, char base>
struct Aho_Corasick : Trie<char_size+1, base>{
using trie = Trie<char_size+1, base>;
const int failure = char_size;
vector<int> correct;
void build(bool heavy = false){
correct.resize(this->size());
rep(i, this->size()){
correct[i] = sz(this->nodes[i].accept);
}
queue<int> que;
rep(i, char_size+1){
if(this->nodes[0].next[i] != -1){
this->nodes[this->nodes[0].next[i]].next[failure] = 0;
que.push(this->nodes[0].next[i]);
}
else{
this->nodes[0].next[i] = 0;
}
}
while(!que.empty()){
auto &now = this->nodes[que.front()];
correct[que.front()] += correct[now.next[failure]];
que.pop();
rep(i, char_size){
if(now.next[i] == -1) continue;
int fail = now.next[failure];
while(this->nodes[fail].next[i] == -1) fail = this->nodes[fail].next[failure];
this->nodes[now.next[i]].next[failure] = this->nodes[fail].next[i];
if(heavy){
auto &u = this->nodes[now.next[i]].accept;
auto &v = this->nodes[this->nodes[fail].next[i]].accept;
vector<int> accept;
set_union(all(u), all(v), back_inserter(accept));
u = accept;
}
que.emplace(now.next[i]);
}
}
}
map<int, int> match(const string &s){
int now = 0;
map<int, int> ret;
for(auto &e: s){
while(this->nodes[now].next[e-base] == -1) now = this->nodes[now].next[failure];
now = this->nodes[now].next[e-base];
for(auto &u: this->nodes[now].accept) ret[u]++;
}
return ret;
}
pii move(int now, const int c){
while(this->nodes[now].next[c] == -1) now = this->nodes[now].next[failure];
now = this->nodes[now].next[c];
return pii(correct[now], now);
}
};
int main(){
int N;
ll L, R;
cin >> N >> L >> R;
Aho_Corasick<10, '0'> trie;
ll p = 1, q = 1;
while(q <= R){
if(q >= L) trie.insert(to_string(q));
p += q, swap(p, q);
}
int K = trie.size();
trie.build();
int dp[N+1][K];
fill(dp[0], dp[N+1], 0);
dp[0][0] = 1;
rep(i, N){
rep(j, K){
rep(k, 10){
auto [p, q] = trie.move(j, k);
if(p == 0) dp[i+1][q] += dp[i][j], dp[i+1][q] %= MOD;
}
}
}
int ans = MOD-1;
rep(i, K) ans += dp[N][i], ans %= MOD;
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0