結果
| 問題 | No.1269 I hate Fibonacci Number |
| ユーザー |
 やむなく
|
| 提出日時 | 2020-10-23 23:28:44 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,140 bytes |
| コンパイル時間 | 2,295 ms |
| コンパイル使用メモリ | 189,796 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-07-21 13:24:50 |
| 合計ジャッジ時間 | 3,679 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 7 WA * 29 |
ソースコード
//// Created by yamunaku on 2020/10/23.//#include <bits/stdc++.h>//#include <atcoder/all>using namespace std;//using namespace atcoder;#define rep(i, n) for(int i = 0; i < (n); i++)#define repl(i, l, r) for(int i = (l); i < (r); i++)#define per(i, n) for(int i = ((n)-1); i >= 0; i--)#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)#define all(x) (x).begin(),(x).end()#define MOD9 998244353#define MOD 1000000007#define IINF 1000000000#define LINF 1000000000000000000#define SP <<" "<<#define CYES cout<<"Yes"<<endl#define CNO cout<<"No"<<endl#define CFS cin.tie(0);ios::sync_with_stdio(false)#define CST(x) cout<<fixed<<setprecision(x)using ll = long long;using ld = long double;using vi = vector<int>;using mti = vector<vector<int>>;using vl = vector<ll>;using mtl = vector<vector<ll>>;using pi = pair<int, int>;using pl = pair<ll, ll>;template<typename T>using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;template<int char_size>struct TrieNode {int nxt[char_size];int exist;ll count;bool flag;vector<int> accept;TrieNode() : exist(0), count(0), flag(false) {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);nodes[node_index].flag = true;} 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());}};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()];correct[que.front()] += correct[now.nxt[FAIL]];que.pop();for (int i = 0; i < char_size; i++) {if (now.nxt[i] == -1) continue;int fail = now.nxt[FAIL];while (this->nodes[fail].nxt[i] == -1) fail = this->nodes[fail].nxt[FAIL];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]);}}}map<int, int> match(const string &str, int now = 0) {map<int, int> result;for (auto &c : str) {while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL];now = this->nodes[now].nxt[c - margin];for (auto &v : this->nodes[now].accept) result[v] += 1;}return result;}pair<int, int> move(const char &c, int now) {int sum = 0;while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL];now = this->nodes[now].nxt[c - margin];sum += correct[now];return {sum, now};}void init() {this->nodes[this->root].count = 1;}mti nxxt;void buildnexxt() {int sz = this->nodes.size();nxxt = mti(sz, vi(10));rep(i, sz) {rep(j, 10) {nxxt[i][j] = this->nodes[i].nxt[j];if (nxxt[i][j] == -1) nxxt[i][j] = nxxt[this->nodes[i].nxt[FAIL]][j];}}}ll moveone() {int sz = this->nodes.size();vl tmp(sz, 0);rep(i, sz) {if (this->nodes[i].flag) continue;ll k = this->nodes[i].count;repl(j, 1, 10) {tmp[nxxt[i][j]] += k;}}ll ans = 0;rep(i, sz) {if (this->nodes[i].flag) continue;tmp[i] %= MOD;ans += tmp[i];this->nodes[i].count = tmp[i];}return ans % MOD;}ll moveall() {int sz = this->nodes.size();vl tmp(sz, 0);rep(i, sz) {if (this->nodes[i].flag) continue;ll k = this->nodes[i].count;rep(j, 10) {tmp[nxxt[i][j]] += k;}}ll ans = 0;rep(i, sz) {if (this->nodes[i].flag) continue;tmp[i] %= MOD;ans += tmp[i];this->nodes[i].count = tmp[i];}return ans % MOD;}};int main() {//CFS;int n;ll l, r;cin >> n >> l >> r;vl f(2, 1);while (f[f.size() - 2] < LINF - f[f.size() - 1]) {f.push_back(f[f.size() - 2] + f[f.size() - 1]);}AhoCorasick<10, '0'> ac;for (auto &x : f) {if (l <= x && x <= r) {ac.add(to_string(x));}}ac.build();ac.buildnexxt();ac.init();ll ans = ac.moveone();repl(i, 1, n) ans = (ans + ac.moveall()) % MOD;cout << ans << endl;return 0;}