結果
| 問題 | No.1269 I hate Fibonacci Number |
| ユーザー |
 noimi
|
| 提出日時 | 2020-10-16 03:41:43 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 223 ms / 3,000 ms |
| コード長 | 22,853 bytes |
| コンパイル時間 | 22,473 ms |
| コンパイル使用メモリ | 354,644 KB |
| 最終ジャッジ日時 | 2025-01-15 07:46:32 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#pragma region Macros#pragma GCC optimize("O3")#pragma GCC target("avx2,avx")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>#define ll long long#define ld long double#define rep2(i, a, b) for(ll i = a; i <= b; ++i)#define rep(i, n) for(ll i = 0; i < n; ++i)#define rep3(i, a, b) for(ll i = a; i >= b; --i)#define pii pair<int, int>#define pll pair<ll, ll>#define pb push_back#define eb emplace_back#define vi vector<int>#define vll vector<ll>#define vpi vector<pii>#define vpll vector<pll>#define overload2(_1, _2, name, ...) name#define vec(type, name, ...) vector<type> name(__VA_ARGS__)#define VEC(type, name, size)\vector<type> name(size);\IN(name)#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))#define VV(type, name, h, w)\vector<vector<type>> name(h, vector<type>(w));\IN(name)#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))#define vvvv(type, name, a, b, c, ...)\vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))#define fi first#define se second#define all(c) begin(c), end(c)#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))using namespace std;string YES[2] = {"NO", "YES"};string Yes[2] = {"No", "Yes"};string yes[2] = {"no", "yes"};template <class T> using pq = priority_queue<T>;template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;#define si(c) (int)(c).size()#define INT(...)\int __VA_ARGS__;\IN(__VA_ARGS__)#define LL(...)\ll __VA_ARGS__;\IN(__VA_ARGS__)#define STR(...)\string __VA_ARGS__;\IN(__VA_ARGS__)#define CHR(...)\char __VA_ARGS__;\IN(__VA_ARGS__)#define DBL(...)\double __VA_ARGS__;\IN(__VA_ARGS__)int scan() { return getchar(); }void scan(int &a) { cin >> a; }void scan(long long &a) { cin >> a; }void scan(char &a) { cin >> a; }void scan(double &a) { cin >> a; }void scan(string &a) { cin >> a; }template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }template <class T> void scan(vector<T> &);template <class T> void scan(vector<T> &a) {for(auto &i : a) scan(i);}template <class T> void scan(T &a) { cin >> a; }void IN() {}template <class Head, class... Tail> void IN(Head &head, Tail &... tail) {scan(head);IN(tail...);}template <class T, class S> inline bool chmax(T &a, S b) {if(a < b) {a = b;return 1;}return 0;}template <class T, class S> inline bool chmin(T &a, S b) {if(a > b) {a = b;return 1;}return 0;}vi iota(int n) {vi a(n);iota(all(a), 0);return a;}template <typename T> vi iota(vector<T> &a, bool greater = false) {vi res(a.size());iota(all(res), 0);sort(all(res), [&](int i, int j) {if(greater) return a[i] > a[j];return a[i] < a[j];});return res;}#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())vector<pll> factor(ll x) {vector<pll> ans;for(ll i = 2; i * i <= x; i++)if(x % i == 0) {ans.push_back({i, 1});while((x /= i) % i == 0) ans.back().second++;}if(x != 1) ans.push_back({x, 1});return ans;}template <class T> vector<T> divisor(T x) {vector<T> ans;for(T i = 1; i * i <= x; i++)if(x % i == 0) {ans.pb(i);if(i * i != x) ans.pb(x / i);}return ans;}template <typename T> void zip(vector<T> &x) {vector<T> y = x;sort(all(y));for(int i = 0; i < x.size(); ++i) { x[i] = lb(y, x[i]); }}int popcount(ll x) { return __builtin_popcountll(x); }struct Setup_io {Setup_io() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(15);}} setup_io;int in() {int x;cin >> x;return x;}ll lin() {unsigned long long x;cin >> x;return x;}// template <typename T> struct edge {// int from, to;// T cost;// int id;// edge(int to, T cost) : from(-1), to(to), cost(cost) {}// edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}// edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id) {}// edge &operator=(const int &x) {// to = x;// return *this;// }// operator int() const { return to; }// };// template <typename T> using Edges = vector<edge<T>>;// using Tree = vector<vector<int>>;// using Graph = vector<vector<int>>;// template <class T> using Wgraph = vector<vector<edge<T>>>;// Graph getG(int n, int m = -1, bool directed = false, int margin = 1) {// Tree res(n);// if(m == -1) m = n - 1;// while(m--) {// int a, b;// cin >> a >> b;// a -= margin, b -= margin;// res[a].emplace_back(b);// if(!directed) res[b].emplace_back(a);// }// return move(res);// }// template <class T> Wgraph<T> getWg(int n, int m = -1, bool directed = false, int margin = 1) {// Wgraph<T> res(n);// if(m == -1) m = n - 1;// while(m--) {// int a, b;// T c;// cin >> a >> b >> c;// a -= margin, b -= margin;// res[a].emplace_back(b, c);// if(!directed) res[b].emplace_back(a, c);// }// return move(res);// }#define i128 __int128_t#define ull unsigned long long int#define TEST\INT(testcases);\while(testcases--)template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {for(auto &e : v) cout << e << " ";cout << endl;return os;}template <class T, class S> ostream &operator<<(ostream &os, const pair<T, S> &p) {cout << "(" << p.fi << ", " << p.se << ")";return os;}template <class S, class T> string to_string(pair<S, T> p) { return "(" + to_string(p.first) + "," + to_string(p.second) + ")"; }template <class A> string to_string(A v) {if(v.empty()) return "{}";string ret = "{";for(auto &x : v) ret += to_string(x) + ",";ret.back() = '}';return ret;}void dump() { cerr << endl; }template <class Head, class... Tail> void dump(Head head, Tail... tail) {cerr << to_string(head) << " ";dump(tail...);}#define endl '\n'#ifdef _LOCAL#undef endl#define debug(x)\cout << #x << ": ";\dump(x)#else#define debug(x)#endif// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());// int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }// ll rndll(ll n) { return uniform_int_distribution<ll>(0, n - 1)(rng); }template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;#pragma endregiontemplate <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()); }};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};}};namespace modular {constexpr ll MOD = 1000000007;const int MAXN = 1100000;template <ll Modulus> class modint;#define mint modint<MOD>#define vmint vector<mint>vector<mint> Inv;mint inv(int x);template <ll Modulus> class modint {public:static constexpr int mod() { return Modulus; }ll a;constexpr modint(const ll x = 0) noexcept : a(((x % Modulus) + Modulus) % Modulus) {}constexpr ll &value() noexcept { return a; }constexpr const ll &value() const noexcept { return a; }constexpr modint operator-() const noexcept { return modint() - *this; }constexpr modint operator+() const noexcept { return *this; }constexpr modint &operator++() noexcept {if(++a == MOD) a = 0;return *this;}constexpr modint &operator--() noexcept {if(!a) a = MOD;a--;return *this;}constexpr modint operator++(int) {modint res = *this;++*this;return res;}constexpr modint operator--(int) {mint res = *this;--*this;return res;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if(a >= Modulus) { a -= Modulus; }return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if(a < rhs.a) { a += Modulus; }a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(const modint rhs) noexcept {a = a * (modular::inv(rhs.a)).a % Modulus;return *this;}constexpr modint pow(long long n) const noexcept {modint x = *this, r = 1;while(n) {if(n & 1) r *= x;x *= x;n >>= 1;}return r;}constexpr modint inv() const noexcept { return pow(Modulus - 2); }constexpr friend modint operator+(const modint &lhs, const modint &rhs) { return modint(lhs) += modint(rhs); }constexpr friend modint operator-(const modint &lhs, const modint &rhs) { return modint(lhs) -= modint(rhs); }constexpr friend modint operator*(const modint &lhs, const modint &rhs) { return modint(lhs) *= modint(rhs); }constexpr friend modint operator/(const modint &lhs, const modint &rhs) { return modint(lhs) /= modint(rhs); }constexpr friend modint operator==(const modint &lhs, const modint &rhs) { return lhs.a == rhs.a; }constexpr friend modint operator!=(const modint &lhs, const modint &rhs) { return lhs.a != rhs.a; }// constexpr friend modint operator^=(const modint &lhs, const modint &rhs) { return modint(lhs) ^= modint(rhs); }};vmint Fact{1, 1}, Ifact{1, 1};mint inv(int n) {if(Inv.empty()) Inv.emplace_back(0), Inv.emplace_back(1);if(Inv.size() > n)return Inv[n];else {for(int i = Inv.size(); i <= n; ++i) Inv.emplace_back(Inv[MOD % i] * (-MOD / i));return Inv[n];}}mint fact(int n) {if(Fact.size() > n)return Fact[n];elsefor(int i = Fact.size(); i <= n; ++i) Fact.emplace_back(Fact[i - 1] * i);return Fact[n];}mint ifact(int n) {if(Ifact.size() > n)return Ifact[n];elsefor(int i = Ifact.size(); i <= n; ++i) Ifact.emplace_back(Ifact[i - 1] * inv(i));return Ifact[n];}mint modpow(ll a, ll n) { return mint(a).pow(n); }mint inv(mint a) { return inv(a.a); }mint ifact(mint a) { return ifact(a.a); }mint fact(mint a) { return fact(a.a); }mint modpow(mint a, ll n) { return modpow(a.a, n); }mint C(int a, int b) {if(a < 0 || b < 0) return 0;if(a < b) return 0;return fact(a) * ifact(b) * ifact(a - b);}mint P(int a, int b) {if(a < 0 || b < 0) return 0;if(a < b) return 0;return fact(a) * ifact(a - b);}ostream &operator<<(ostream &os, mint a) {os << a.a;return os;}istream &operator>>(istream &is, mint &a) {ll x;is >> x;a = x;return is;}struct modinfo {int mod, root;};constexpr modinfo base0{1045430273, 3};constexpr modinfo base1{1051721729, 6};constexpr modinfo base2{1053818881, 7};using mint0 = modint<base0.mod>;using mint1 = modint<base1.mod>;using mint2 = modint<base2.mod>;using Poly = vmint;template <int mod> void FMT(vector<modint<mod>> &f, bool inv = false) {using V = vector<modint<mod>>;static V g(30), ig(30);if(g.front().a == 0) {modint<mod> root = 2;while((root.pow((mod - 1) / 2)).a == 1) root += 1;rep(i, 30) g[i] = -(root.pow((mod - 1) >> (i + 2))), ig[i] = g[i].inv();}int n = size(f);if(!inv) {for(int m = n; m >>= 1;) {modint<mod> w = 1;for(int s = 0, k = 0; s < n; s += 2 * m) {for(int i = s, j = s + m; i < s + m; ++i, ++j) {auto x = f[i], y = f[j] * w;if(x.a >= mod) x.a -= mod;f[i].a = x.a + y.a, f[j].a = x.a + (mod - y.a);}w *= g[__builtin_ctz(++k)];}}} else {for(int m = 1; m < n; m *= 2) {modint<mod> w = 1;for(int s = 0, k = 0; s < n; s += 2 * m) {for(int i = s, j = s + m; i < s + m; ++i, ++j) {auto x = f[i], y = f[j];f[i] = x + y, f[j].a = x.a + (mod - y.a), f[j] *= w;}w *= ig[__builtin_ctz(++k)];}}}modint<mod> c;if(inv)c = modint<mod>(n).inv();elsec = 1;for(auto &&e : f) e *= c;}Poly operator-(Poly f) {for(auto &&e : f) e = -e;return f;}Poly &operator+=(Poly &l, const Poly &r) {l.resize(max(l.size(), r.size()));rep(i, r.size()) l[i] += r[i];return l;}Poly operator+(Poly l, const Poly &r) { return l += r; }Poly &operator-=(Poly &l, const Poly &r) {l.resize(max(l.size(), r.size()));rep(i, r.size()) l[i] -= r[i];return l;}Poly operator-(Poly l, const Poly &r) { return l -= r; }Poly &operator<<=(Poly &f, size_t n) { return f.insert(f.begin(), n, 0), f; }Poly operator<<(Poly f, size_t n) { return f <<= n; }Poly &operator>>=(Poly &f, size_t n) { return f.erase(f.begin(), f.begin() + min(f.size(), n)), f; }Poly operator>>(Poly f, size_t n) { return f >>= n; }constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;using M0 = modint<mod0>;using M1 = modint<mod1>;using M2 = modint<mod2>;template <int mod> void mul(vector<modint<mod>> &l, vector<modint<mod>> &r) {int n = size(l), m = size(r), sz = 1 << __lg(2 * (n + m - 1) - 1);l.resize(sz), FMT<mod>(l);r.resize(sz), FMT<mod>(r);rep(i, sz) l[i] *= r[i];FMT<mod>(l, true);l.resize(n + m - 1);}Poly operator*(const Poly &l, const Poly &r) {if(l.empty() or r.empty()) return Poly();int n = size(l), m = size(r), sz = 1 << __lg(2 * (n + m - 1) - 1);vector<M0> l0(n), r0(m);vector<M1> l1(n), r1(m);vector<M2> l2(n), r2(m);rep(i, n) l0[i] = l[i].a, l1[i] = l[i].a, l2[i] = l[i].a;rep(i, m) r0[i] = r[i].a, r1[i] = r[i].a, r2[i] = r[i].a;mul<mod0>(l0, r0), mul<mod1>(l1, r1), mul<mod2>(l2, r2);Poly res(n + m - 1);// garnerstatic constexpr M1 inv0 = 613999507;static constexpr M2 inv1 = 1147332803, inv0m1 = 45381342;static constexpr mint m0 = mod0, m0m1 = m0 * mod1;rep(i, n + m - 1) {int y0 = l0[i].a;int y1 = (inv0 * (l1[i] - y0)).a;int y2 = (inv0m1 * (l2[i] - y0) - inv1 * y1).a;res[i] = m0 * y1 + m0m1 * y2 + y0;}return res;}Poly &operator*=(Poly &l, const Poly &r) { return l = l * r; }Poly integ(const Poly &f) {Poly res(f.size() + 1);for(int i = 1; i < (int)res.size(); ++i) res[i] = f[i - 1] / i;return res;}struct Prd {deque<Poly> deq;Prd() = default;void emplace(const Poly &f) { deq.emplace_back(f); }Poly calc() {if(deq.empty()) return {1};sort(all(deq), [&](const Poly &f, const Poly &g) { return si(f) < si(g); });while(deq.size() > 1) {deq.emplace_back(deq[0] * deq[1]);for(int i = 0; i < 2; ++i) deq.pop_front();}return deq.front();}};Poly prd(vector<Poly> &v) {Prd p;for(auto &e : v) p.emplace(e);return p.calc();}// Poly deriv(const Poly &f) {// if(f.size() == 0) return Poly();// Poly res(f.size() - 1);// rep(i, res.size()) res[i] = f[i + 1] * (i + 1);// return res;// }ostream &operator<<(ostream &os, const Poly &a) {for(auto e : a) cout << e.a << " ";return os;}} // namespace modularusing namespace modular;int main() {INT(n);LL(L, R);AhoCorasick<10, '0'> trie;{ll p = 0, q = 1;while(p + q <= R) {swap(p, q);q = p + q;if(L <= q and q <= R) trie.add(to_string(q));}}int m = trie.size();trie.build();vmint dp(m);dp[0] = 1;while(n--) {vmint nxt(m);rep(i, m) {for(char c = '0'; c <= '9'; ++c) {auto [p, q] = trie.move(c, i);if(!p) nxt[q] += dp[i];}}swap(dp, nxt);}cout << accumulate(all(dp), (mint)0) - 1 << endl;}