結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
![]() |
提出日時 | 2021-09-27 23:07:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 136 ms / 3,000 ms |
コード長 | 15,677 bytes |
コンパイル時間 | 3,146 ms |
コンパイル使用メモリ | 242,928 KB |
最終ジャッジ日時 | 2025-01-24 18:37:09 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
コンパイルメッセージ
main.cpp: In function ‘void cp_lib_io::flush()’: main.cpp:53:25: warning: ignoring return value of ‘ssize_t write(int, const void*, size_t)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 53 | void flush() { write(STDOUT_FILENO, begin(obuf), optr - begin(obuf)); optr = begin(obuf); } | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#pragma GCC optimize("fast-math")// begin "cp-lib/prelude.hpp"#include <bits/stdc++.h>#ifdef LOCAL# include <dbg.h>#else# define dbg(...) do {} while (0)#endif#define cp_lib_4th(_1, _2, _3, x, ...) x#define cp_lib_rep(i, l, r) for (int i = (l); (i) < (r); ++(i))#define cp_lib_rep0(i, r) cp_lib_rep(i, 0, r)#define rep(...) cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__)#define cp_lib_repr(i, r, l, ...) for (int i = (r); (i) >= (l); --(i))#define repr(...) cp_lib_repr(__VA_ARGS__, 0)#define all(a) ::begin(a),::end(a)#define trav(a, b) for (auto&& a : (b))using namespace std;using ll = long long;using ld = long double;[[maybe_unused]] static constexpr int INF = int(1e9 + 5);[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;template <class C> int sz(const C& c) { return int(::size(c)); }// end "cp-lib/prelude.hpp"// begin "cp-lib/io.hpp"// begin "_assert.hpp"#ifdef CP_LIB_DEBUG#define cp_lib_assert(expr) \do { if (!(expr)) { \::cerr << "assertion failed: " << #expr << " (" << __FILE__ << ':' << __LINE__ << ")\n"; \::abort(); \} } while (0)#else#define cp_lib_assert(expr)#endif// end "_assert.hpp"// begin "modint/_detect.hpp"namespace cp_lib_modint { struct ModIntTag {}; }// end "modint/_detect.hpp"#include <unistd.h>namespace cp_lib_io {constexpr int BUF_SIZE = 1 << 20;array<char, BUF_SIZE> ibuf, obuf;char *iptr = data(ibuf), *iend = iptr, *optr = data(obuf);template <class T, class = void> struct is_tuple_like : false_type {};template <class T> struct is_tuple_like<T, void_t<tuple_element_t<0, T>>> : true_type {};template <class T> struct is_std_array : false_type {};template <class T, size_t I> struct is_std_array<array<T, I>> : true_type {};void flush() { write(STDOUT_FILENO, begin(obuf), optr - begin(obuf)); optr = begin(obuf); }void ensure_write(int l) { if (end(obuf) - optr < l) flush(); }int _flush_atexit = []{ atexit(flush); return 0; }();void refill() {memmove(begin(ibuf), iptr, iend - iptr);iend -= iptr - begin(ibuf);iptr = begin(ibuf);iend += read(STDIN_FILENO, iend, end(ibuf) - iend);}void skip_ensure_read(int l) {do {while (iptr != iend && *iptr <= ' ') ++iptr;if (iend - iptr < l) refill();} while (*iptr <= ' ');}template <class T, class T2 = remove_reference_t<remove_cv_t<T>>>void print(T&& val) {if constexpr (is_same_v<T2, char>)ensure_write(2), *optr++ = val;else if constexpr (is_integral_v<T2> && !is_same_v<T2, bool>) {ensure_write(numeric_limits<T>::digits10 + 1 + is_signed_v<T2>);if (val < 0) { *optr++ = '-'; print(make_unsigned_t<T2>(-make_unsigned_t<T2>(val))); return; }array<char, 128> tmp;char* tptr = end(tmp);remove_const_t<T2> val_copy = val;do { *--tptr = char('0' + val_copy % 10), val_copy /= 10; } while (val_copy);memcpy(optr, tptr, end(tmp) - tptr);optr += end(tmp) - tptr;#if __cpp_lib_to_chars >= 201611} else if constexpr (is_floating_point_v<T2>) {ensure_write(64);auto res = to_chars(optr, end(obuf), val, chars_format::fixed, 30);cp_lib_assert(res.ec == errc());optr = res.ptr;#endif} else if constexpr (is_convertible_v<T, string_view>) {string_view sv(val);if (sz(sv) + 1 <= end(obuf) - optr)memcpy(optr, data(sv), sz(sv)), optr += sz(sv);elseflush(), write(STDOUT_FILENO, data(sv), sz(sv));} else {if constexpr (is_same_v<T2, bool> || is_same_v<T2, vector<bool>::reference>)print(int(val));else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T2>)print(decltype(T2::mod())(val));else if constexpr (is_tuple_like<T2>() && !is_std_array<T2>())apply([](auto&&... items) { (print(items), ...); }, forward<T>(val));elsetrav(item, val) print(item);return;}*optr++ = ' ';}template <class T>void read(T& val) {if constexpr (is_same_v<T, char>)skip_ensure_read(1), val = *iptr++;else if constexpr (is_same_v<T, bool> || is_same_v<T, vector<bool>::reference>) {uint8_t ival; read(ival), val = bool(ival);} else if constexpr (is_base_of_v<cp_lib_modint::ModIntTag, T>) {ll ival; read(ival); val = T(ival);} else if constexpr (is_integral_v<T>) {skip_ensure_read(numeric_limits<T>::digits10 + 1 + is_signed_v<T>);if (is_signed_v<T> && *iptr == '-') {++iptr;make_unsigned_t<T> uval;read(uval);val = T(-uval);} else {val = 0;while (iptr != iend && *iptr > ' ') val = T(10 * val + (*iptr++ - '0'));}#if __cpp_lib_to_chars >= 201611} else if constexpr (is_floating_point_v<T>) {skip_ensure_read(128);auto res = from_chars(iptr, iend, val);assert(res.ec == errc());iptr = const_cast<char*>(res.ptr);#endif} else if constexpr (is_same_v<T, string>) {val = string();skip_ensure_read(1);do {auto* after = iptr;while (after != iend && *after > ' ') ++after;copy(iptr, after, back_inserter(val));if ((iptr = after) == iend)refill();elsebreak;} while (iptr != iend);} else if constexpr (is_tuple_like<T>() && !is_std_array<T>())apply([](auto&... items) { (read(items), ...); }, val);elsetrav(item, val) read(item);}}using cp_lib_io::flush;template <class... Args>void print(Args&&... args) { (cp_lib_io::print(forward<Args>(args)), ...); }template <class... Args>void println(Args&&... args) {if (sizeof...(Args) > 0)(cp_lib_io::print(forward<Args>(args)), ...), *(cp_lib_io::optr - 1) = '\n';elsecp_lib_io::ensure_write(1), *cp_lib_io::optr++ = '\n';}template <class... Args>void printlns(Args&&... args) {((cp_lib_io::print(forward<Args>(args)), *(cp_lib_io::optr - 1) = '\n'), ...);}template <class... Args>void read(Args&... args) { (cp_lib_io::read(args), ...); }// end "cp-lib/io.hpp"// begin "cp-lib/modint/static-montgomery.hpp"// begin "_base.hpp"// begin "../math/ext-gcd.hpp"template <class I>constexpr enable_if_t<is_signed_v<I>, array<I, 3>> ext_gcd(I a, I b) {I x(1), y(0), x1(0), y1(1);while (b) {I t = a / b;tie(x, x1) = pair(x1, x - t * x1);tie(y, y1) = pair(y1, y - t * y1);tie(a, b) = pair(b, a - t * b);}return {a, x, y};}// end "../math/ext-gcd.hpp"namespace cp_lib_modint {template <class Self, class Int>struct Base : ModIntTag {static_assert(is_same_v<Int, uint32_t> || is_same_v<Int, uint64_t>);friend constexpr Self operator+(Self l, Self r) { return l += r; }friend constexpr Self operator-(Self l, Self r) { return l -= r; }friend constexpr Self operator*(Self l, Self r) { return l *= r; }friend constexpr Self operator/(Self l, Self r) { return l * r.inv(); }friend constexpr Self& operator/=(Self& l, Self r) { return l *= r.inv(); }friend constexpr Self operator+(Self x) { return x; }friend constexpr Self operator-(Self x) { return Self(0) - x; }friend constexpr Self& operator++(Self& x) { return x += Self(1); }friend constexpr Self& operator--(Self& x) { return x -= Self(1); }friend constexpr Self operator++(Self& x, int) { auto y = x; ++x; return y; }friend constexpr Self operator--(Self& x, int) { auto y = x; --x; return y; }#define CP_LIB_DEF(op) \template <class T, enable_if_t<is_integral_v<T>, int> = 0> \friend constexpr auto operator op(T l, Self r) { return Self(l) op r; }CP_LIB_DEF(==) CP_LIB_DEF(!=) CP_LIB_DEF(<) CP_LIB_DEF(+) CP_LIB_DEF(-) CP_LIB_DEF(*) CP_LIB_DEF(/)#undef CP_LIB_DEFtemplate <class T>constexpr enable_if_t<is_integral_v<T>, Self> pow(T e) const {Self r(1), b(*(Self*)(this));for (; e; b *= b, e >>= 1)if (e & 1) r *= b;return r;}constexpr optional<Self> try_inv() const {if (Self::is_prime())return *(Self*)this == Self() ? nullopt : optional(pow(Self::mod() - 2));auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod()));return (abs(g) == 1 ? optional(Self(x)) : nullopt);}constexpr Self inv() const {if (Self::is_prime()) return pow(Self::mod() - 2);auto [g, x, _] = ext_gcd(ll(*(Self*)this), ll(Self::mod()));cp_lib_assert(abs(g) == 1);return x;}friend ostream& operator<<(ostream& out, Self m) { return out << uint64_t(m); }friend istream& operator>>(istream& in, Self& m) { ll x; in >> x; m = x; return in; }protected:Int i = 0;};template <class Int> using Wide = conditional_t<is_same_v<uint64_t, Int>, unsigned __int128, uint64_t>;}struct ModIntRaw {};// end "_base.hpp"namespace cp_lib_modint {template <class Int, Int Mod, bool IsPrime>class StaticMontgomery : public Base<StaticMontgomery<Int, Mod, IsPrime>, Int> {static_assert(Mod % 2 && Mod < (1ull << (sizeof(Int) * 8 - 2)));static constexpr Int INV = []{Int inv = Mod;rep(_, __builtin_ctz(sizeof(Int) * 8) - 1) inv *= 2 - Mod * inv;return inv;}();static constexpr Int R2 = Int(-Wide<Int>(Mod) % Mod);static constexpr Int reduce(Wide<Int> x) {return Int((x - Int(x) * INV * Wide<Int>(Mod))>> (sizeof(Int) * 8)) + Mod;}constexpr Int norm(Int x) const { return x >= Mod ? x - Mod : x; }public:static constexpr Int mod() { return Mod; }static constexpr bool is_prime() { return IsPrime; }StaticMontgomery() = default;template <class T, enable_if_t<is_unsigned_v<T>, int> = 0>constexpr StaticMontgomery(T x) { this->i = reduce(Wide<Int>(uint64_t(x) % Mod) * R2); }template <class T, enable_if_t<is_signed_v<T>, int> = 0>constexpr StaticMontgomery(T x) { this->i = reduce(Wide<Int>(ll(x) % ll(Mod) + ll(Mod)) * R2); }constexpr StaticMontgomery(Int x, ModIntRaw) { this->i = x; }template <class T, enable_if_t<is_integral_v<T>, int> = 0>constexpr explicit operator T() const { return T(norm(reduce(this->i))); }constexpr bool operator==(StaticMontgomery r) const { return norm(this->i) == norm(r.i); }constexpr bool operator!=(StaticMontgomery r) const { return norm(this->i) != norm(r.i); }constexpr bool operator<(StaticMontgomery r) const { return norm(this->i) < norm(r.i); }constexpr StaticMontgomery& operator+=(StaticMontgomery r) {if ((this->i += r.i) >= 2 * Mod)this->i -= 2 * Mod;return *this;}constexpr StaticMontgomery& operator-=(StaticMontgomery r) {if (make_signed_t<Int>(this->i -= r.i) < 0)this->i += 2 * Mod;return *this;}constexpr StaticMontgomery& operator*=(StaticMontgomery r) {return *this = {reduce(Wide<Int>(this->i) * r.i), {}};}};}template <uint32_t Mod, bool IsPrime> using StaticMontgomeryInt = cp_lib_modint::StaticMontgomery<uint32_t, Mod, IsPrime>;template <uint64_t Mod, bool IsPrime> using StaticMontgomeryInt64 = cp_lib_modint::StaticMontgomery<uint64_t, Mod, IsPrime>;// end "cp-lib/modint/static-montgomery.hpp"template <int K>struct Trie {static constexpr bool Sparse = (K == -1);vector<array<int, K>> t{1};vector<int> cnt = {INF};size_t size() const { return ::size(t); }int next(int v, int c) const { return t[v][c]; }template <class It, class ItEnd, class T = typename iterator_traits<It>::value_type>int add(It it, ItEnd it_end, T base = (is_same_v<T, char> ? 'a' : T(0))) {int v = 0;for (; it != it_end; ++it) {if (!t[v][*it - base])t[v][*it - base] = sz(t), t.emplace_back(), cnt.emplace_back();v = t[v][*it - base];++cnt[v];}return v;}template <class It, class ItEnd, class T = typename iterator_traits<It>::value_type>void remove(It it, ItEnd it_end, T base = (is_same_v<T, char> ? 'a' : T(0))) {int v = 0;for (; it != it_end && --cnt[next(v, *it - base)]; v = next(v, *it++ - base))cp_lib_assert(next(v, *it - base));if (it != it_end)t[v][*it - base] = 0;}};template <int W>class BitTrie : public Trie<2> {array<bool, W> bits;void to_bits(uint64_t x) { rep(i, W) bits[W - 1 - i] = (x >> i) & 1; }template <bool Max>uint64_t xor_eval(uint64_t x) const {uint64_t ans = 0;for (int i = W - 1, v = 0, bit = int((x >> i) & 1); i >= 0; bit = int((x >> --i) & 1)) {if (next(v, bit ^ Max))v = next(v, bit ^ Max), ans ^= (uint64_t(Max) << i);elsev = next(v, !bit ^ Max), ans ^= (uint64_t(!Max) << i);}return ans;}public:uint64_t xor_min(uint64_t x) const { return xor_eval<false>(x); }uint64_t xor_max(uint64_t x) const { return xor_eval<true>(x); }int add(uint64_t x) { to_bits(x); return Trie<2>::add(all(bits)); }void remove(uint64_t x) { to_bits(x); Trie<2>::remove(all(bits)); }};template <int K = 26>struct AhoCorasick : Trie<K> {template <class F>void build(F&& f) {queue<array<int, 4>> q;q.push({0, -1, 0, -1});while (sz(q)) {auto [v, c, p, plink] = q.front(); q.pop();int link = (p ? this->next(plink, c) : 0);rep(i, K) {if (this->next(v, i))q.push({this->next(v, i), i, v, link});elsethis->t[v][i] = (v ? this->next(link, i) : 0);}if (v)f(v, link, c, p);}}};int main() {int n; ll l, r; read(n, l, r);vector fib = {0ll, 1ll};while (fib.back() <= r)fib.push_back(fib.back() + fib[sz(fib) - 2]);AhoCorasick<10> ac;vector<bool> is_end = {false};trav(fi, fib) {if (fi < l || r < fi)continue;auto s = to_string(fi);int v = ac.add(all(s), '0');is_end.resize(sz(ac));is_end[v] = true;}ac.build([&](int v, int link, int, int) {is_end[v] = is_end[v] || is_end[link];});int m = sz(ac);using MI = StaticMontgomeryInt<int(1e9) + 7, true>;vector dp(n + 1, vector(m, MI(0)));dp[0][0] = 1;rep(i, n) rep(j, m) rep(k, 10)if (!is_end[j])dp[i + 1][ac.next(j, k)] += dp[i][j];MI ans = 0;rep(i, m)if (!is_end[i])ans += dp[n][i];println(ans - 1);}