結果
問題 | No.911 ラッキーソート |
ユーザー | hashiryo |
提出日時 | 2023-04-10 17:51:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 28,191 bytes |
コンパイル時間 | 10,518 ms |
コンパイル使用メモリ | 351,816 KB |
実行使用メモリ | 61,084 KB |
最終ジャッジ日時 | 2024-10-06 04:03:26 |
合計ジャッジ時間 | 13,494 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | WA | - |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | WA | - |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | WA | - |
testcase_14 | AC | 39 ms
5,248 KB |
testcase_15 | AC | 36 ms
5,248 KB |
testcase_16 | AC | 39 ms
5,248 KB |
testcase_17 | AC | 42 ms
5,248 KB |
testcase_18 | WA | - |
testcase_19 | AC | 41 ms
5,248 KB |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 161 ms
51,652 KB |
testcase_23 | AC | 34 ms
5,248 KB |
testcase_24 | WA | - |
testcase_25 | AC | 91 ms
22,568 KB |
testcase_26 | AC | 16 ms
5,248 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 9 ms
5,248 KB |
testcase_30 | AC | 3 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | WA | - |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | WA | - |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | AC | 8 ms
5,248 KB |
testcase_41 | AC | 36 ms
5,248 KB |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | AC | 36 ms
5,248 KB |
testcase_45 | AC | 36 ms
5,248 KB |
testcase_46 | AC | 36 ms
5,248 KB |
testcase_47 | AC | 37 ms
5,248 KB |
testcase_48 | AC | 37 ms
5,248 KB |
ソースコード
// #define _GLIBCXX_DEBUG#include <bits/stdc++.h>// clang-format offstd::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;returnstd::reverse(s.begin(),s.end()),os<<s;}#define checkpoint() (void(0))#define debug(x) (void(0))#define debugArray(x,n) (void(0))#define debugMatrix(x,h,w) (void(0))// clang-format on#ifdef __LOCAL// clang-format off#undef checkpoint#undef debug#undef debugArray#undef debugMatrixtemplate<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x;return os << '}';}template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";#define func_LINE_FILE NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?" [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)#endif// clang-format on#include <type_traits>#include <cassert>template <class Int> constexpr inline Int mod_inv(Int a, Int mod) {static_assert(std::is_signed_v<Int>);Int x= 1, y= 0, b= mod;for (Int q= 0, z= 0, c= 0; b;) z= x, c= a, x= y, y= z - y * (q= a / b), a= b, b= c - b * q;return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod;}namespace math_internal {using namespace std;using u8= uint8_t;using u32= uint32_t;using u64= uint64_t;using i64= int64_t;using u128= __uint128_t;#define CE constexpr#define IL inline#define NORM \if (n >= mod) n-= mod; \return n#define PLUS(U, M) \CE IL U plus(U l, U r) const { \if (l+= r; l >= M) l-= M; \return l; \}#define DIFF(U, C, M) \CE IL U diff(U l, U r) const { \if (l-= r; l >> C) l+= M; \return l; \}#define SGN(U) \static CE IL U set(U n) { return n; } \static CE IL U get(U n) { return n; } \static CE IL U norm(U n) { return n; }template <class u_t, class du_t, u8 B, u8 A> struct MP_Mo {u_t mod;CE MP_Mo(): mod(0), iv(0), r2(0) {}CE MP_Mo(u_t m): mod(m), iv(inv(m)), r2(-du_t(mod) % mod) {}CE IL u_t mul(u_t l, u_t r) const { return reduce(du_t(l) * r); }PLUS(u_t, mod << 1)DIFF(u_t, A, mod << 1)CE IL u_t set(u_t n) const { return mul(n, r2); }CE IL u_t get(u_t n) const {n= reduce(n);NORM;}CE IL u_t norm(u_t n) const { NORM; }private:u_t iv, r2;static CE u_t inv(u_t n, int e= 6, u_t x= 1) { return e ? inv(n, e - 1, x * (2 - x * n)) : x; }CE IL u_t reduce(const du_t &w) const { return u_t(w >> B) + mod - ((du_t(u_t(w) * iv) * mod) >> B); }};struct MP_Na {u32 mod;CE MP_Na(): mod(0){};CE MP_Na(u32 m): mod(m) {}CE IL u32 mul(u32 l, u32 r) const { return u64(l) * r % mod; }PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32)};struct MP_Br { // mod < 2^31u32 mod;CE MP_Br(): mod(0), s(0), x(0) {}CE MP_Br(u32 m): mod(m), s(31 - __builtin_clz(m - 1) + 64), x(((u128(1) << s) + m - 1) / m) {}CE IL u32 mul(u32 l, u32 r) const { return rem(u64(l) * r); }PLUS(u32, mod) DIFF(u32, 31, mod) SGN(u32) private: u8 s;u64 x;CE IL u64 quo(u64 n) const { return (u128(x) * n) >> s; }CE IL u32 rem(u64 n) const { return n - quo(n) * mod; }};struct MP_Br2 { // 2^20 < mod <= 2^41u64 mod;CE MP_Br2(): mod(0), x(0) {}CE MP_Br2(u64 m): mod(m), x((u128(1) << 84) / m) {}CE IL u64 mul(u64 l, u64 r) const { return rem(u128(l) * r); }PLUS(u64, mod << 1)DIFF(u64, 63, mod << 1)static CE IL u64 set(u64 n) { return n; }CE IL u64 get(u64 n) const { NORM; }CE IL u64 norm(u64 n) const { NORM; }private:u64 x;CE IL u128 quo(const u128 &n) const { return (n * x) >> 84; }CE IL u64 rem(const u128 &n) const { return n - quo(n) * mod; }};struct MP_D2B1 {u8 s;u64 mod, d, v;CE MP_D2B1(): s(0), mod(0), d(0), v(0) {}CE MP_D2B1(u64 m): s(__builtin_clzll(m)), mod(m), d(m << s), v(u128(-1) / d) {}CE IL u64 mul(u64 l, u64 r) const { return rem((u128(l) * r) << s) >> s; }PLUS(u64, mod) DIFF(u64, 63, mod) SGN(u64) private: CE IL u64 rem(const u128 &u) const {u128 q= (u >> 64) * v + u;u64 r= u64(u) - (q >> 64) * d - d;if (r > u64(q)) r+= d;if (r >= d) r-= d;return r;}};template <class u_t, class MP> CE u_t pow(u_t x, u64 k, const MP &md) {for (u_t ret= md.set(1);; x= md.mul(x, x))if (k & 1 ? ret= md.mul(ret, x) : 0; !(k>>= 1)) return ret;}#undef NORM#undef PLUS#undef DIFF#undef SGN#undef CE}namespace math_internal {#define CE constexprstruct m_b {};struct s_b: m_b {};template <class mod_t> CE bool is_modint_v= is_base_of_v<m_b, mod_t>;template <class mod_t> CE bool is_staticmodint_v= is_base_of_v<s_b, mod_t>;template <class MP, u64 MOD> struct SB: s_b {protected:static CE MP md= MP(MOD);};template <class Int, class U, class B> struct MInt: public B {using Uint= U;static CE inline auto mod() { return B::md.mod; }CE MInt(): x(0) {}CE MInt(const MInt &r): x(r.x) {}template <class T, enable_if_t<is_modint_v<T>, nullptr_t> = nullptr> CE MInt(T v): x(B::md.set(v.val() % B::md.mod)) {}template <class T, enable_if_t<is_convertible_v<T, __int128_t>, nullptr_t> = nullptr> CE MInt(T n): x(B::md.set((n < 0 ? ((n= (-n) % B::md.mod) ? B::md.mod - n : n) : n % B::md.mod))) {}CE MInt operator-() const { return MInt() - *this; }#define FUNC(name, op) \CE MInt name const { \MInt ret; \ret.x= op; \return ret; \}FUNC(operator+(const MInt &r), B::md.plus(x, r.x))FUNC(operator-(const MInt &r), B::md.diff(x, r.x))FUNC(operator*(const MInt &r), B::md.mul(x, r.x))FUNC(pow(u64 k), math_internal::pow(x, k, B::md))#undef FUNCCE MInt operator/(const MInt &r) const { return *this * r.inv(); }CE MInt &operator+=(const MInt &r) { return *this= *this + r; }CE MInt &operator-=(const MInt &r) { return *this= *this - r; }CE MInt &operator*=(const MInt &r) { return *this= *this * r; }CE MInt &operator/=(const MInt &r) { return *this= *this / r; }CE bool operator==(const MInt &r) const { return B::md.norm(x) == B::md.norm(r.x); }CE bool operator!=(const MInt &r) const { return !(*this == r); }CE bool operator<(const MInt &r) const { return B::md.norm(x) < B::md.norm(r.x); }CE inline MInt inv() const { return mod_inv<Int>(val(), B::md.mod); }CE inline Uint val() const { return B::md.get(x); }friend ostream &operator<<(ostream &os, const MInt &r) { return os << r.val(); }friend istream &operator>>(istream &is, MInt &r) {i64 v;return is >> v, r= MInt(v), is;}private:Uint x;};template <u64 MOD> using ModInt= conditional_t < (MOD < (1 << 30)) & MOD, MInt<int, u32, SB<MP_Mo<u32, u64, 32, 31>, MOD>>, conditional_t < (MOD <(1ull << 62)) & MOD, MInt<i64, u64, SB<MP_Mo<u64, u128, 64, 63>, MOD>>, conditional_t<MOD<(1u << 31), MInt<int, u32, SB<MP_Na, MOD>>,conditional_t<MOD<(1ull << 32), MInt<i64, u32, SB<MP_Na, MOD>>, conditional_t<MOD <= (1ull << 41), MInt<i64, u64, SB<MP_Br2, MOD>>, MInt<i64, u64, SB<MP_D2B1, MOD>>>>>>>;#undef CE}using math_internal::ModInt, math_internal::is_modint_v, math_internal::is_staticmodint_v;template <class mod_t, size_t LM> mod_t get_inv(int n) {static_assert(is_modint_v<mod_t>);static const auto m= mod_t::mod();static mod_t dat[LM];static int l= 1;if (l == 1) dat[l++]= 1;while (l <= n) dat[l++]= dat[m % l] * (m - m / l);return dat[n];}template <class symbol_t> class Automaton {std::vector<int> table;std::vector<int8_t> info;std::vector<symbol_t> alph;const int m;template <template <class, class> class Map, class state_t, class F, class G, class H> void build(const state_t &initial_state, const F &transition,const G &is_accept, const H &abs_reject) {static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);static_assert(std::is_same_v<bool, std::invoke_result_t<H, state_t>>);Map<state_t, int> encode;std::vector<state_t> decode;int ts= 0;decode.push_back(initial_state), encode.emplace(initial_state, ts++);for (int i= 0, k= 0; i < ts; ++i) {auto s= decode[i];table.resize(table.size() + m);for (int j= 0; j < m; ++j) {if (auto t= transition(s, j); abs_reject(t)) table[k++]= -1;else if (auto it= encode.find(t); it != encode.end()) table[k++]= it->second;else table[k++]= ts, decode.push_back(t), encode.emplace(t, ts++);}}info.resize(ts);for (int i= ts; i--;) info[i]= is_accept(decode[i]);}Automaton(const std::vector<symbol_t> &alphabet): alph(alphabet), m(alph.size()) {}public:template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<state_t, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> =nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept): alph(alphabet), m(alph.size()) {std::sort(alph.begin(), alph.end());auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };if constexpr (std::is_integral_v<state_t>) build<std::unordered_map>(initial_state, tr, is_accept, [](const state_t &) { return false; });else build<std::map>(initial_state, tr, is_accept, [](const state_t &) { return false; });}template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<state_t, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> =nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept, const state_t&abs_rej_state): alph(alphabet), m(alph.size()) {std::sort(alph.begin(), alph.end());auto tr= [&](const state_t &s, int i) { return transition(s, alph[i]); };if constexpr (std::is_integral_v<state_t>) build<std::unordered_map>(initial_state, tr, is_accept, [abs_rej_state](const state_t &s) { return s ==abs_rej_state; });else build<std::map>(initial_state, tr, is_accept, [abs_rej_state](const state_t &s) { return s == abs_rej_state; });}template <class state_t, class F, class G, std::enable_if_t<std::is_same_v<std::set<state_t>, std::invoke_result_t<F, state_t, symbol_t>>, std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G &is_accept):alph(alphabet), m(alph.size()) {static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);std::sort(alph.begin(), alph.end());auto tr= [&](const std::set<state_t> &s, int i) {std::set<state_t> ret;for (const auto &x: s) {auto ys= transition(x, alph[i]);ret.insert(ys.begin(), ys.end());}return ret;};auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };build<std::map>(std::set<state_t>({initial_state}), tr, ac, [](const std::set<state_t> &s) { return s == std::set<state_t>(); });}template <class state_t, class F, class G, class H, std::enable_if_t<std::is_same_v<std::set<state_t>, std::invoke_result_t<F, state_t, symbol_t>>,std::nullptr_t> = nullptr> Automaton(const std::vector<symbol_t> &alphabet, const state_t &initial_state, const F &transition, const G&is_accept, const H &eps_trans): alph(alphabet), m(alph.size()) {static_assert(std::is_same_v<bool, std::invoke_result_t<G, state_t>>);static_assert(std::is_same_v<std::set<state_t>, std::invoke_result_t<H, state_t>>);std::sort(alph.begin(), alph.end());auto eps_closure= [&](std::set<state_t> s) {for (std::set<state_t> t; s != t;) {t= s;for (const auto &x: t) {auto ys= eps_trans(x);s.insert(ys.begin(), ys.end());}}return s;};auto tr= [&](const std::set<state_t> &s, int i) {std::set<state_t> ret;for (const auto &x: s) {auto ys= transition(x, alph[i]);ret.insert(ys.begin(), ys.end());}return eps_closure(ret);};auto ac= [&](const std::set<state_t> &s) { return std::any_of(s.begin(), s.end(), is_accept); };build<std::map>(eps_closure({initial_state}), tr, ac, [](const std::set<state_t> &s) { return s == std::set<state_t>(); });}size_t alphabet_size() const { return m; }Automaton operator&(const Automaton &r) const {assert(alph == r.alph);const int S= info.size();auto tr= [&](int s, int q) {auto [s1, s0]= std::div(s, S);int t1= r.table[s1 * m + q], t0= table[s0 * m + q];return t0 == -1 || t1 == -1 ? -1 : t1 * S + t0;};auto ac= [&](int s) {auto [s1, s0]= std::div(s, S);return info[s0] == 1 && r.info[s1] == 1;};Automaton ret(alph);return ret.build<std::unordered_map>(0, tr, ac, [](int s) { return s == -1; }), ret;}template <class T, class A, class F> T dp_run(int n, const A &op, const T &ti, const F &f, const T &init) const {static_assert(std::is_same_v<T, std::invoke_result_t<A, T, T>>);static_assert(std::is_same_v<T, std::invoke_result_t<F, T, symbol_t, int>>);const size_t S= info.size();std::queue<std::pair<int, int>> que;T dp[2][S], ret= ti;bool in[2][S];for (std::fill_n(dp[0], S, ti), std::fill_n(dp[1], S, ti), std::fill_n(in[0], S, 0), std::fill_n(in[1], S, 0), dp[0][0]= init, que.emplace(0, 0),in[0][0]= 1; que.size();) {auto [s, i]= que.front();bool b= i & 1;T tmp= dp[b][s];if (que.pop(), in[b][s]= 0, dp[b][s]= ti; i == n) {if (info[s] == 1) ret= op(ret, tmp);continue;}auto l= table.cbegin() + s * m;for (int j= m; j--;)if (int t= l[j]; t != -1)if (dp[!b][t]= op(dp[!b][t], f(tmp, alph[j], i)); !in[!b][t]) que.emplace(t, i + 1), in[!b][t]= 1;}return ret;}template <class T> T num(int n) const {return dp_run(n, [](const T &l, const T &r) { return l + r; }, T(), [](const T &x, const auto &, auto) { return x; }, T(1));}};using namespace std;// https://atcoder.jp/contests/abc235/tasks/abc235_fnamespace ABC235F {signed main() {cin.tie(0);ios::sync_with_stdio(0);using Mint= ModInt<998244353>;string N;int M;cin >> N >> M;int n= N.length();int c= 0;for (int i= 0; i < M; i++) {int C;cin >> C, c|= 1 << C;}std::vector<int> alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};auto tr0= [&](int s, int q) {if (s >= n) return s;int c= N[s] - '0';if (q > c) return n + 1;if (q < c) return n;return s + 1;};auto ac0= [&](int s) { return s == n; };Automaton dfa_le(alp, 0, tr0, ac0, n + 1);auto tr1= [&](int s, int q) { return s | ((q || s) << q); };auto ac1= [&](int s) { return (s & c) == c; };Automaton dfa_variety(alp, 0, tr1, ac1);auto dfa= dfa_le & dfa_variety;using T= array<Mint, 2>;auto op= [](const T &l, const T &r) { return T{l[0] + r[0], l[1] + r[1]}; };auto f= [](const T &v, int a, int) { return T{v[0] * 10 + v[1] * a, v[1]}; };cout << dfa.dp_run(n, op, T{0, 0}, f, T{0, 1})[0] << '\n';return 0;}} // namespace ABC235F// https://atcoder.jp/contests/agc015/tasks/agc015_dnamespace AGC015D {signed main() {cin.tie(0);ios::sync_with_stdio(false);vector alphabet= {0, 1};using state_t= set<pair<int64_t, int64_t>>;auto tr= [&](const state_t &S, int c) -> set<state_t> {set<state_t> ret;if (c == 0) {state_t T;bool isok= true;for (auto [a, b]: S) {if (a= (a + 1) / 2, b/= 2; a > b) {isok= false;break;}T.emplace(a, b);}if (isok) ret.insert(T);} else {int sz= S.size();for (int s= 1 << sz; --s;)for (int t= s;; --t&= s) {state_t T;bool isok= true;auto it= S.cbegin();for (int j= sz; j--; ++it) {auto [a, b]= *it;auto a0= (a + 1) / 2, b0= b / 2;auto a1= a / 2, b1= (b + 1) / 2 - 1;if ((t >> j) & 1) {if (a0 > b0 || a1 > b1) {isok= false;break;}T.emplace(a0, b0), T.emplace(a1, b1);} else if ((s >> j) & 1) {if (a1 > b1) {isok= false;break;}T.emplace(a1, b1);} else {if (a0 > b0) {isok= false;break;}T.emplace(a0, b0);}}if (isok) ret.insert(T);if (!t) break;}}return ret;};int64_t A, B;cin >> A >> B;Automaton nfa(alphabet, state_t({{A, B}}), tr, [](const auto &) { return true; });cout << nfa.num<int64_t>(60) << '\n';return 0;}} // namespace AGC015D// https://atcoder.jp/contests/abc050/tasks/arc066_bnamespace ARC066B {signed main() {cin.tie(0);ios::sync_with_stdio(false);using Mint= ModInt<int(1e9 + 7)>;using symbol_t= array<bool, 2>;vector<symbol_t> alp= {{0, 0}, {0, 1}, {1, 0}, {1, 1}};using state_t= int64_t;auto tr0= [&](state_t s, symbol_t c) {if (c[0] == 0) return s / 2;else return (s + 1) / 2 - 1;};auto tr1= [&](state_t s, symbol_t c) {if (c[1] == 0) return s / 2;else return (s + 1) / 2 - 1;};int64_t N;cin >> N;Automaton dfa_le0(alp, N, tr0, [&](int64_t) { return true; }, state_t(-1));Automaton dfa_le1(alp, N, tr1, [&](int64_t) { return true; }, state_t(-1));auto tr= [&](int s, symbol_t c) {set<int> ret;for (int a= 2; a--;)for (int b= 2; b--;)if ((a ^ b) == c[0] && ((a + b + s) & 1) == c[1]) ret.insert((a + b + s) / 2);return ret;};Automaton nfa(alp, 0, tr, [&](int s) { return s == 0; });auto dfa= dfa_le0 & dfa_le1 & nfa;cout << dfa.num<Mint>(60) << '\n';return 0;}}// https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2587namespace AOJ_2587 {signed main() {cin.tie(0);ios::sync_with_stdio(false);int N;vector<int> low, high;vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};while (cin >> N && N != 0) {low.resize(N), high.resize(N);for (int i= 0; i < N; ++i) cin >> low[i] >> high[i];using state_t= array<int, 2>;auto tr= [&](state_t s, int c) -> set<state_t> {auto [i, j]= s;if (i >= N) return {};auto [l1, l0]= div(low[i], 10);auto [h1, h0]= div(high[i], 10);if (j == 1) {if (l0 <= c) return {{i + 1, 0}};} else if (j == 2) return {{i + 1, 0}};else if (j == 3) {if (c <= h0) return {{i + 1, 0}};} else if (j == 4) {if (l0 <= c && c <= h0) return {{i + 1, 0}};} else {if (c == 0) return {};if (l1 == h1) {if (c == l1) return {{i, 4}};} else {if (c == l1) return {{i, 1}};if (l1 < c && c < h1) return {{i, 2}};if (c == h1) return {{i, 3}};}}return {};};auto eps= [&](state_t s) -> set<state_t> {auto [i, j]= s;if (i >= N) return {};if (j == 0 && (low[i] / 10) == 0) {if ((high[i] / 10) == 0) return {{i, 4}};else return {{i, 1}};}return {};};auto ac= [&](state_t s) { return s[0] == N && s[1] == 0; };Automaton nfa(alp, state_t{0, 0}, tr, ac, eps);int64_t ans= 0;for (int i= N; i <= 2 * N; ++i) ans+= nfa.num<int64_t>(i);cout << ans << '\n';}return 0;}} // namespace AOJ_2587// https://onlinejudge.u-aizu.ac.jp/problems/0570namespace AOJ_0570 {signed main() {cin.tie(0);ios::sync_with_stdio(false);using Mint= ModInt<10000>;string A, B;cin >> A >> B;int M;cin >> M;int n= B.length();A= string(n - A.length(), '0') + A;vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};auto tr_a= [&](int s, int c) {if (s >= n) return s;int d= A[s] - '0';if (c < d) return n + 1;if (c > d) return n;return s + 1;};auto tr_b= [&](int s, int c) {if (s >= n) return s;int d= B[s] - '0';if (c > d) return n + 1;if (c < d) return n;return s + 1;};auto ac0= [&](int s) { return s == n; };Automaton dfa_a(alp, 0, tr_a, ac0, n + 1), dfa_b(alp, 0, tr_b, ac0, n + 1);auto tr_m= [&](int s, int c) { return (s * 10 + c) % M; };Automaton dfa_m(alp, 0, tr_m, [](int s) { return s == 0; });using state_t= array<int, 2>;auto tr_zz= [&](state_t s, int c) -> state_t {auto [d, t]= s;if (d == -2) {if (c == 0) return {-2, -2};else return {c, -2};}if (d == c) return {-1, -1};if (t == -2) return {c, d < c};if (d < c) {if (t == 1) return {-1, -1};else return {c, 1};} else {if (t == 0) return {-1, -1};else return {c, 0};}return {-1, -1};};Automaton dfa_zz(alp, state_t{-2, -2}, tr_zz, [](state_t) { return true; }, state_t{-1, -1});debug(dfa_zz.num<Mint>(n));debug((dfa_a & dfa_b).num<Mint>(n));debug((dfa_a & dfa_b & dfa_m).num<Mint>(n));auto dfa= dfa_a & dfa_b & dfa_m & dfa_zz;cout << dfa.num<Mint>(n) << '\n';return 0;}}// https://yukicoder.me/problems/no/315namespace yukicoder_315 {signed main() {cin.tie(0);ios::sync_with_stdio(false);using Mint= ModInt<int(1e9 + 7)>;string A, B;cin >> A >> B;int P;cin >> P;vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};int n_a= A.length(), n_b= B.length();for (int i= n_a; i--;) {if (A[i] > '0') {--A[i];break;}A[i]= '9';}auto tr_a= [&](int s, int c) {if (s >= n_a) return s;int d= A[s] - '0';if (c < d) return n_a;if (c > d) return n_a + 1;return s + 1;};auto tr_b= [&](int s, int c) {if (s >= n_b) return s;int d= B[s] - '0';if (c < d) return n_b;if (c > d) return n_b + 1;return s + 1;};auto ac_a= [&](int s) { return s == n_a; };auto ac_b= [&](int s) { return s == n_b; };Automaton dfa_a(alp, 0, tr_a, ac_a, n_a + 1), dfa_b(alp, 0, tr_b, ac_b, n_b + 1);auto tr_3= [&](int s, int c) {if (s == -1 || c == 3) return -1;return (s + c) % 3;};Automaton dfa_3(alp, 0, tr_3, [](int s) { return s <= 0; });auto dfa1= dfa_a & dfa_3;auto dfa2= dfa_b & dfa_3;Mint ans= dfa2.num<Mint>(n_b) - dfa1.num<Mint>(n_a);while (P % 10 == 0) P/= 10, --n_a, --n_b;Automaton dfa_a2(alp, 0, tr_a, ac_a, n_a + 1), dfa_b2(alp, 0, tr_b, ac_b, n_b + 1);auto tr_P= [&](int s, int c) { return (s * 10 + c) % P; };Automaton dfa_P(alp, 0, tr_P, [](int s) { return s == 0; });auto dfa3= dfa_a2 & dfa_3 & dfa_P;auto dfa4= dfa_b2 & dfa_3 & dfa_P;ans-= dfa4.num<Mint>(n_b) - dfa3.num<Mint>(n_a);cout << ans << '\n';return 0;}}// https://yukicoder.me/problems/no/1417namespace yukicode_1417 {signed main() {cin.tie(0);ios::sync_with_stdio(0);using Mint= ModInt<int(1e9 + 7)>;vector alp= {1, 2, 3, 4, 5, 6, 7, 8, 9};string N;cin >> N;int n= N.length();auto tr_le= [&](int s, int c) {if (s >= n) return s;int d= N[s] - '0';if (c < d) return n;if (c > d) return n + 1;return s + 1;};Automaton dfa_le(alp, 0, tr_le, [&](int s) { return s == n; }, n + 1);auto tr_prod= [](int s, int c) { return s * c % 100; };Automaton dfa_prod(alp, 1, tr_prod, [](int s) { return s == 0; });Mint ans= 0;for (int i= 1; i < n; ++i) ans+= dfa_prod.num<Mint>(i);auto dfa= dfa_le & dfa_prod;ans+= dfa.num<Mint>(n);cout << ans << '\n';return 0;}}// https://yukicoder.me/problems/no/685namespace yukicoder_685 {signed main() {cin.tie(0);ios::sync_with_stdio(0);using Mint= ModInt<int(1e9 + 7)>;using symbol_t= array<int, 2>;vector<symbol_t> alp= {{0, 0}, {0, 1}, {1, 0}, {1, 1}};int64_t N;cin >> N;auto tr_le= [&](int64_t s, symbol_t c) {if (c[1]) return (s + 1) / 2 - 1;else return s / 2;};Automaton dfa_le(alp, N, tr_le, [](int64_t) { return true; }, int64_t(-1));auto tr_xy= [&](bool s, symbol_t c) {if (c[0] < c[1]) s= 1;else if (c[0] > c[1]) s= 0;return s;};Automaton dfa_xy(alp, false, tr_xy, [](bool s) { return s; });auto tr_ax= [&](bool s, symbol_t c) {bool a= c[0] & c[1], x= c[0] ^ c[1];if (a < x) s= 1;else if (a > x) s= 0;return s;};Automaton dfa_ax(alp, false, tr_ax, [](bool s) { return s; });auto tr_xo= [&](bool s, symbol_t c) {bool x= c[0] ^ c[1], o= c[0] | c[1];if (x < o) s= 1;else if (x > o) s= 0;return s;};Automaton dfa_xo(alp, false, tr_xo, [](bool s) { return s; });auto dfa= dfa_le & dfa_xy & dfa_ax & dfa_xo;cout << dfa.num<Mint>(60) << '\n';return 0;}}// https://yukicoder.me/problems/no/737namespace yukicoder_737 {signed main() {cin.tie(0);ios::sync_with_stdio(0);using Mint= ModInt<int(1e9 + 7)>;vector alp= {0, 1};int64_t N;cin >> N;auto tr= [&](int s, int c) {if (s >= 60) return s;int d= (N >> (59 - s)) & 1;if (c < d) return 60;if (c > d) return 61;return s + 1;};Automaton dfa(alp, 0, tr, [&](int s) { return s == 60; }, 61);using T= array<Mint, 4>;auto op= [&](const T &l, const T &r) {T ret;for (int i= 4; i--;) ret[i]= l[i] + r[i];return ret;};auto f= [&](T x, int c, int) {x[0]+= x[0], x[1]+= x[1];if (c) {x[0]+= x[1] + x[2] + x[3];x[1]+= x[3];x[2]+= x[3];}return x;};cout << dfa.dp_run(60, op, T{0, 0, 0, 0}, f, T{0, 0, 0, 1})[0] << '\n';return 0;}}// https://yukicoder.me/problems/no/911namespace yukicoder_911 {signed main() {cin.tie(0);ios::sync_with_stdio(0);int N;cin >> N;int64_t L, R;cin >> L >> R;vector<int64_t> A(N);for (int i= 0; i < N; ++i) cin >> A[i];vector alp= {0, 1};auto tr_l= [&](int s, int c) {if (s >= 60) return s;int d= (L >> (59 - s)) & 1;if (c < d) return 61;if (c > d) return 60;return s + 1;};auto tr_r= [&](int s, int c) {if (s >= 60) return s;int d= (R >> (59 - s)) & 1;if (c < d) return 60;if (c > d) return 61;return s + 1;};auto ac0= [&](int s) { return s == 60; };Automaton dfa_l(alp, 0, tr_l, ac0, 61), dfa_r(alp, 0, tr_r, ac0, 61);using state_t= pair<vector<int>, int>;state_t rej= make_pair(vector<int>(), -1);state_t init= make_pair(vector<int>{0, N}, 0);auto tr_x= [&](const state_t &s, int c) -> state_t {const auto &[sep, i]= s;if (i >= 60) return s;const int n= sep.size();vector<int> nsep{0};for (int j= 0; j + 1 < n; ++j) {int bg= sep[j], ed= sep[j + 1];for (int k= bg; k + 1 < ed; ++k) {int l= ((A[k] >> (59 - i)) & 1) ^ c, r= ((A[k + 1] >> (59 - i)) & 1) ^ c;if (l > r) return rej;if (l < r) nsep.push_back(k + 1);}nsep.push_back(ed);}return {nsep, i + 1};};auto ac_x= [&](const state_t &s) {const auto &[sep, i]= s;return sep.size() == N + 1;};Automaton dfa_x(alp, init, tr_x, ac_x, rej);auto dfa= dfa_l & dfa_r & dfa_x;cout << dfa.num<int64_t>(60) << '\n';return 0;}}signed main() {cin.tie(0);ios::sync_with_stdio(0);// ABC235F::main();// AGC015D::main();// ARC066B::main();// AOJ_2587::main();// AOJ_0570::main();// yukicoder_315::main();// yukicode_1417::main();// yukicoder_685::main();// yukicoder_737::main();yukicoder_911::main();return 0;}