結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
|
提出日時 | 2020-10-26 09:56:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 367 ms / 3,000 ms |
コード長 | 4,626 bytes |
コンパイル時間 | 3,086 ms |
コンパイル使用メモリ | 209,548 KB |
最終ジャッジ日時 | 2025-01-15 15:50:52 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#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+1];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+1) ans += dp[N][i], ans %= MOD;cout << ans << endl;}