結果
問題 | No.2159 Filling 4x4 array |
ユーザー | hashiryo |
提出日時 | 2023-04-10 01:04:45 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 23,684 bytes |
コンパイル時間 | 6,447 ms |
コンパイル使用メモリ | 265,040 KB |
実行使用メモリ | 144,372 KB |
最終ジャッジ日時 | 2024-10-05 06:22:27 |
合計ジャッジ時間 | 12,654 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | AC | 6 ms
5,248 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
ソースコード
// #define _GLIBCXX_DEBUG // #include <bits/stdc++.h> #include <iostream> #include <vector> #include <set> #include <map> #include <array> #include <queue> #include <algorithm> // 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 <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>>); std::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]); }; build(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]); }; build(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::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(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(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, [](T l, T r) { return l + r; }, T(), [](T x, 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/2159 namespace yukicoder_2159 { signed main() { cin.tie(0); ios::sync_with_stdio(false); using Mint= ModInt<998244353>; using symbol_t= array<array<bool, 3>, 3>; vector<symbol_t> alp(1 << 9); for (int s= 1 << 9; s--;) { auto &x= alp[s]; for (int i= 3; i--;) for (int j= 3; j--;) x[i][j]= (s >> (i * 3 + j)) & 1; } using state_t= array<array<int, 4>, 2>; state_t rej; for (int i= 2; i--;) for (int j= 4; j--;) rej[i][j]= -1; auto tr= [&](const state_t &s, const symbol_t &c) -> state_t { array<array<bool, 4>, 4> box; for (int i= 3; i--;) for (int j= 3; j--;) box[i][j]= c[i][j]; for (int i= 3; i--;) { box[i][3]= (s[0][i] & 1); for (int j= 3; j--;) box[i][3]^= box[i][j]; } for (int j= 3; j--;) { box[3][j]= (s[1][j] & 1); for (int i= 3; i--;) box[3][j]^= box[i][j]; } box[3][3]= (s[0][3] & 1); for (int j= 3; j--;) box[3][3]^= box[3][j]; bool b= (s[1][3] & 1); for (int i= 4; i--;) b^= box[i][3]; if (b) return rej; auto ret= s; for (int i= 4; i--;) for (int j= 4; j--;) ret[0][i]-= box[i][j]; for (int i= 4; i--;) for (int j= 4; j--;) ret[1][j]-= box[i][j]; for (int i= 2; i--;) for (int j= 4; j--;) { if (ret[i][j] < 0) return rej; ret[i][j]/= 2; } return ret; }; auto ac= [&](const state_t &s) { for (int i= 2; i--;) for (int j= 4; j--;) if (s[i][j]) return false; return true; }; state_t init; for (int i= 2; i--;) for (int j= 4; j--;) cin >> init[i][j], init[i][j]-= 4; Automaton dfa(alp, init, tr, ac, rej); cout << dfa.num<Mint>(30) << '\n'; return 0; } } // namespace yukicoder_2159 signed main() { cin.tie(0); ios::sync_with_stdio(0); // ABC235F::main(); // AGC015D::main(); // ARC066B::main(); // AOJ_2587::main(); // AOJ_0570::main(); yukicoder_2159::main(); return 0; }