結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
|
提出日時 | 2020-10-26 12:40:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 3,000 ms |
コード長 | 5,112 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 210,396 KB |
最終ジャッジ日時 | 2025-01-15 15:53:26 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;};//Aho-Corasick法(複数文字列についてパターンマッチするオートマトンを構築する)//計算量 構築:O(∑|S[i]|)、遷移:O(1)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 FAIL = char_size;vector<int> correct;void build(bool heavy = true){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[FAIL] = 0;que.push(this->nodes[0].next[i]);}else{this->nodes[0].next[i] = 0;}}while(!que.empty()){auto &now = this->nodes[que.front()];int fail = now.next[FAIL];correct[que.front()] += correct[fail];que.pop();rep(i, char_size){if(now.next[i] != -1){this->nodes[now.next[i]].next[FAIL] = 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]);}else{now.next[i] = this->nodes[fail].next[i];}}}}map<int, int> match(int now, const string &s) const{map<int, int> ret;for(auto &c: s){now = this->nodes[now].next[c-base];for(auto &u: this->nodes[now].accept) ret[u]++;}return ret;}map<int, int> match(const string &s) const {return match(0, s);}pli move(int now, const char &c) const{now = this->nodes[now].next[c-base];return pli(correct[now], now);}pli move(const char &c) const {return move(0, c);}pli move(int now, const string &s) const{ll sum = 0;for(auto &c: s){pli p = move(now, c);sum += p.first, now = p.second;}return pli(sum, now);}pli move(const string &s) const {return move(0, s);}};//https://yukicoder.me/problems/no/430//https://yukicoder.me/problems/no/1269int 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, '0'+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;}