結果
| 問題 | No.1953 ８ |
| ユーザー |
 hashiryo
|
| 提出日時 | 2023-04-10 19:16:56 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 29,358 bytes |
| コンパイル時間 | 9,177 ms |
| コンパイル使用メモリ | 358,252 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-06 05:38:20 |
| 合計ジャッジ時間 | 13,051 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
6,820 KB |
| testcase_01 | AC | 4 ms
6,816 KB |
| testcase_02 | AC | 5 ms
6,816 KB |
| testcase_03 | AC | 4 ms
6,816 KB |
| testcase_04 | AC | 4 ms
6,816 KB |
| testcase_05 | AC | 3 ms
6,816 KB |
| testcase_06 | AC | 3 ms
6,816 KB |
| testcase_07 | AC | 3 ms
6,820 KB |
| testcase_08 | AC | 3 ms
6,820 KB |
| testcase_09 | AC | 3 ms
6,816 KB |
| testcase_10 | AC | 4 ms
6,816 KB |
| testcase_11 | AC | 3 ms
6,816 KB |
| testcase_12 | AC | 4 ms
6,820 KB |
| testcase_13 | AC | 3 ms
6,820 KB |
| testcase_14 | AC | 4 ms
6,820 KB |
| testcase_15 | AC | 3 ms
6,816 KB |
| testcase_16 | AC | 4 ms
6,820 KB |
| testcase_17 | AC | 4 ms
6,816 KB |
| testcase_18 | AC | 4 ms
6,816 KB |
| testcase_19 | AC | 4 ms
6,820 KB |
| testcase_20 | AC | 4 ms
6,816 KB |
| testcase_21 | AC | 4 ms
6,820 KB |
| testcase_22 | AC | 5 ms
6,816 KB |
| testcase_23 | AC | 4 ms
6,816 KB |
| testcase_24 | AC | 5 ms
6,820 KB |
| testcase_25 | AC | 5 ms
6,820 KB |
| testcase_26 | AC | 5 ms
6,820 KB |
| testcase_27 | AC | 4 ms
6,816 KB |
| testcase_28 | AC | 4 ms
6,820 KB |
| testcase_29 | AC | 3 ms
6,816 KB |
ソースコード
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::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;return std::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 debugMatrix
template<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^31
u32 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^41
u64 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 constexpr
struct 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 FUNC
CE 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_f
namespace 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_d
namespace 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_b
namespace 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/2587
namespace 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/0570
namespace 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/315
namespace 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/1417
namespace 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/685
namespace 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/737
namespace 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 <= -1) return s;
int d= (N >> s) & 1;
if (c < d) return -1;
if (c > d) return -2;
return s - 1;
};
Automaton dfa(
alp, 59, tr, [&](int s) { return s == -1; }, -2);
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/911
namespace 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 <= -1) return s;
int d= (L >> s) & 1;
if (c < d) return -2;
if (c > d) return -1;
return s - 1;
};
auto tr_r= [&](int s, int c) {
if (s <= -1) return s;
int d= (R >> s) & 1;
if (c < d) return -1;
if (c > d) return -2;
return s - 1;
};
auto ac0= [&](int s) { return s == -1; };
Automaton dfa_l(alp, 60, tr_l, ac0, -2), dfa_r(alp, 60, tr_r, ac0, -2);
using state_t= pair<vector<int>, int>;
state_t rej= make_pair(vector<int>(), -1);
state_t init= make_pair(vector<int>{0, N}, 60);
auto tr_x= [&](const state_t &s, int c) -> state_t {
const auto &[sep, i]= s;
if (i <= -1) 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] >> i) & 1) ^ c, r= ((A[k + 1] >> 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>(61) << '\n';
return 0;
}
}
// https://yukicoder.me/problems/no/1953
namespace yukicoder_1953 {
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
vector alp= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto tr_le= [&](int64_t s, int c) { return (s - c + 10) / 10 - 1; };
auto ac_le= [&](int64_t) { return true; };
auto tr_0= [&](bool, int c) -> bool { return c; };
auto ac_0= [&](bool s) { return s; };
Automaton dfa_0(alp, false, tr_0, ac_0);
using T= array<int64_t, 2>;
auto op= [&](T l, T r) {
T ret;
ret[0]= l[0] + r[0], ret[1]= l[1] + r[1];
return ret;
};
auto f= [&](T x, int c, int) {
if (c == 4 || c == 6 || c == 9 || c == 0) x[0]+= x[1];
else if (c == 8) x[0]+= 2 * x[1];
return x;
};
int64_t K;
cin >> K;
int64_t l= 0, h= 1ll << 60;
while (h - l > 1) {
int64_t N= (h + l) / 2;
int n= 0;
for (auto m= N; m; m/= 10) ++n;
Automaton dfa_le(alp, N, tr_le, ac_le, int64_t(-1));
auto dfa= dfa_le & dfa_0;
int64_t x= dfa.dp_run(n, op, T{0, 0}, f, T{0, 1})[0];
for (int i= 1; i < n; ++i) x+= dfa_0.dp_run(i, op, T{0, 0}, f, T{0, 1})[0];
if (x == K) {
cout << N << '\n';
return 0;
}
if (x < K) l= N;
else h= N;
}
cout << -1 << '\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();
yukicoder_1953::main();
return 0;
}