結果
| 問題 | No.3043 括弧列の数え上げ |
| ユーザー |
 MtSaka
|
| 提出日時 | 2025-02-28 21:49:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 37,306 bytes |
| コンパイル時間 | 1,945 ms |
| コンパイル使用メモリ | 211,000 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2025-02-28 21:49:53 |
| 合計ジャッジ時間 | 3,240 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
ソースコード
#line 2 "library/template/template.hpp"#include <bits/stdc++.h>#line 3 "library/template/alias.hpp"using ll = long long;using ull = unsigned long long;using ld = long double;using i128 = __int128_t;using u128 = __uint128_t;using pi = std::pair<int, int>;using pl = std::pair<ll, ll>;using vi = std::vector<int>;using vl = std::vector<ll>;using vs = std::vector<std::string>;using vc = std::vector<char>;using vvl = std::vector<vl>;using vd = std::vector<double>;using vp = std::vector<pl>;using vb = std::vector<bool>;template <typename T>struct infinity {static constexpr T max = std::numeric_limits<T>::max();static constexpr T min = std::numeric_limits<T>::min();static constexpr T value = std::numeric_limits<T>::max() / 2;static constexpr T mvalue = std::numeric_limits<T>::min() / 2;};template <typename T>constexpr T INF = infinity<T>::value;constexpr ll inf = INF<ll>;constexpr ld EPS = 1e-8;constexpr ld PI = 3.1415926535897932384626;constexpr int dx[8] = {-1, 0, 1, 0, 1, -1, -1, 1};constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};#line 3 "library/template/macro.hpp"#ifndef __COUNTER__#define __COUNTER__ __LINE__#endif#define SELECT4(a, b, c, d, e, ...) e#define SELECT3(a, b, c, d, ...) d#define REP_1(a, c) for (ll REP_##c = 0; REP_##c < (ll)(a); ++REP_##c)#define REP1(a) REP_1(a, __COUNTER__)#define REP2(i, a) for (ll i = 0; i < (ll)(a); ++i)#define REP3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)#define REP4(i, a, b, c) for (ll i = (ll)(a); i < (ll)(b); i += (ll)(c))#define rep(...) SELECT4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)#define RREP_1(a, c) for (ll RREP_##c = (ll)(a) - 1; RREP_##c >= 0; --RREP_##c)#define RREP1(a) RREP_1(a, __COUNTER__)#define RREP2(i, a) for (ll i = (ll)(a) - 1; i >= 0; --i)#define RREP3(i, a, b) for (ll i = (ll)(b) - 1; i >= (ll)(a); --i)#define rrep(...) SELECT3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)#define all(v) std::begin(v), std::end(v)#define rall(v) std::rbegin(v), std::rend(v)#define INT(...) \int __VA_ARGS__; \scan(__VA_ARGS__)#define LL(...) \ll __VA_ARGS__; \scan(__VA_ARGS__)#define STR(...) \string __VA_ARGS__; \scan(__VA_ARGS__)#define CHR(...) \char __VA_ARGS__; \scan(__VA_ARGS__)#define DBL(...) \double __VA_ARGS__; \scan(__VA_ARGS__)#define LD(...) \ld __VA_ARGS__; \scan(__VA_ARGS__)#define pb push_back#define eb emplace_back#line 3 "library/template/type-traits.hpp"#line 5 "library/template/type-traits.hpp"template <typename T, typename... Args>struct function_traits_impl {using return_type = T;static constexpr std::size_t arg_size = sizeof...(Args);template <std::size_t idx>using argument_type = typename std::tuple_element<idx, std::tuple<Args...>>::type;using argument_types = std::tuple<Args...>;};template <typename>struct function_traits_helper;template <typename T, typename Tp, typename... Args>struct function_traits_helper<T (Tp::*)(Args...)> : function_traits_impl<T, Args...> {};template <typename T, typename Tp, typename... Args>struct function_traits_helper<T (Tp::*)(Args...) const> : function_traits_impl<T, Args...> {};template <typename T, typename Tp, typename... Args>struct function_traits_helper<T (Tp::*)(Args...)&> : function_traits_impl<T, Args...> {};template <typename T, typename Tp, typename... Args>struct function_traits_helper<T (Tp::*)(Args...) const&> : function_traits_impl<T, Args...> {};template <typename F>using function_traits = function_traits_helper<decltype(&std::remove_reference<F>::type::operator())>;template <typename F>using function_return_type = typename function_traits<F>::return_type;template <typename F, std::size_t idx>using function_argument_type = typename function_traits<F>::template argument_type<idx>;template <typename F>using function_argument_types = typename function_traits<F>::argument_types;template <class T>using is_signed_int = std::integral_constant<bool, (std::is_integral<T>::value && std::is_signed<T>::value) || std::is_same<T, __int128_t>::value>;template <class T>using is_unsigned_int = std::integral_constant<bool, (std::is_integral<T>::value && std::is_unsigned<T>::value) || std::is_same<T, __uint128_t>::value>;template <class T>using is_int = std::integral_constant<bool, is_signed_int<T>::value || is_unsigned_int<T>::value>;template <typename T, typename = void>struct is_range : std::false_type {};template <typename T>struct is_range<T,decltype(all(std::declval<typename std::add_lvalue_reference<T>::type>()), (void)0)> : std::true_type {};template <std::size_t size>struct int_least {static_assert(size <= 128, "size must be less than or equal to 128");using type = typename std::conditional<size <= 8, std::int_least8_t,typename std::conditional<size <= 16, std::int_least16_t,typename std::conditional<size <= 32, std::int_least32_t,typename std::conditional<size <= 64, std::int_least64_t, __int128_t>::type>::type>::type>::type;};template <std::size_t size>using int_least_t = typename int_least<size>::type;template <std::size_t size>struct uint_least {static_assert(size <= 128, "size must be less than or equal to 128");using type = typename std::conditional<size <= 8, std::uint_least8_t,typename std::conditional<size <= 16, std::uint_least16_t,typename std::conditional<size <= 32, std::uint_least32_t,typename std::conditional<size <= 64, std::uint_least64_t, __uint128_t>::type>::type>::type>::type;};template <std::size_t size>using uint_least_t = typename uint_least<size>::type;template <typename T>using double_size_int = int_least<std::numeric_limits<T>::digits * 2 + 1>;template <typename T>using double_size_int_t = typename double_size_int<T>::type;template <typename T>using double_size_uint = uint_least<std::numeric_limits<T>::digits * 2>;template <typename T>using double_size_uint_t = typename double_size_uint<T>::type;template <typename T>using double_size = typename std::conditional<std::is_signed<T>::value, double_size_int<T>, double_size_uint<T>>::type;template <typename T>using double_size_t = typename double_size<T>::type;#line 2 "library/template/in.hpp"#include <unistd.h>#line 5 "library/template/in.hpp"namespace fastio {template <std::size_t BUFF_SIZE = 1 << 17, int decimal_precision = 16>struct Scanner {private:template <typename, typename = void>struct has_scan : std::false_type {};template <class T>struct has_scan<T, decltype(std::declval<T>().scan(std::declval<Scanner&>()), (void)0)> : std::true_type {};int fd;char buffer[BUFF_SIZE + 1];int idx, sz;bool state;inline void load() {int len = sz - idx;if (idx < len) return;std::memcpy(buffer, buffer + idx, len);sz = len + read(fd, buffer + len, BUFF_SIZE - len);idx = 0;buffer[sz] = 0;}inline char cur() {if (idx == sz) load();if (idx == sz) {state = false;return '\0';}return buffer[idx];}inline void next() {if (idx == sz) load();if (idx == sz) return;idx++;}public:Scanner() : Scanner(0) {}explicit Scanner(int fd) : fd(fd), idx(0), sz(0), state(true) {}explicit Scanner(FILE* file) : fd(fileno(file)), idx(0), sz(0), state(true) {}inline char scan_char() {if (idx == sz) load();return (idx == sz ? '\0' : buffer[idx++]);}Scanner ignore(int n = 1) {if (idx + n > sz) load();idx += n;return (*this);}inline void skip_space() {if (idx == sz) load();while (('\t' <= cur() && cur() <= '\r') || cur() == ' ') {if (++idx == sz) load();}}void scan(char& a) {skip_space();a = scan_char();}void scan(std::string& a) {skip_space();a.clear();while (cur() != '\0' && (buffer[idx] < '\t' || '\r' < buffer[idx]) && buffer[idx] != ' ') {a += scan_char();}}template <std::size_t len>void scan(std::bitset<len>& a) {skip_space();if (idx + len > sz) load();rrep(i, len) a[i] = (buffer[idx++] != '0');}template <typename T, typename std::enable_if<is_int<T>::value && !has_scan<T>::value>::type* = nullptr>void scan(T& a) {skip_space();bool neg = false;if constexpr (std::is_signed<T>::value || std::is_same_v<T, __int128_t>) {if (cur() == '-') {neg = true;next();}}if (idx + 40 > sz && (idx == sz || ('0' <= buffer[sz - 1] && buffer[sz - 1] <= '9'))) load();a = 0;while ('0' <= buffer[idx] && buffer[idx] <= '9') {a = a * 10 + (buffer[idx++] & 15);}if constexpr (std::is_signed<T>::value || std::is_same<T, __int128_t>::value) {if (neg) a = -a;}}template <typename T, typename std::enable_if<std::is_floating_point<T>::value && !has_scan<T>::value>::type* = nullptr>void scan(T& a) {skip_space();bool neg = false;if (cur() == '-') {neg = true;next();}a = 0;while ('0' <= cur() && cur() <= '9') {a = a * 10 + (scan_char() & 15);}if (cur() == '.') {next();T n = 0, d = 1;for (int i = 0; '0' <= cur() && cur() <= '9' && i < decimal_precision; ++i) {n = n * 10 + (scan_char() & 15);d *= 10;}while ('0' <= cur() && cur() <= '9') next();a += n / d;}if (neg) a = -a;}private:template <std::size_t i, typename... Args>void scan(std::tuple<Args...>& a) {if constexpr (i < sizeof...(Args)) {scan(std::get<i>(a));scan<i + 1, Args...>(a);}}public:template <typename... Args>void scan(std::tuple<Args...>& a) {scan<0, Args...>(a);}template <typename T, typename U>void scan(std::pair<T, U>& a) {scan(a.first);scan(a.second);}template <typename T, typename std::enable_if<is_range<T>::value && !has_scan<T>::value>::type* = nullptr>void scan(T& a) {for (auto& i : a) scan(i);}template <typename T, typename std::enable_if<has_scan<T>::value>::type* = nullptr>void scan(T& a) {a.scan(*this);}void operator()() {}template <typename Head, typename... Tail>void operator()(Head& head, Tail&... tail) {scan(head);operator()(std::forward<Tail&>(tail)...);}template <typename T>Scanner& operator>>(T& a) {scan(a);return *this;}explicit operator bool() const { return state; }friend Scanner& getline(Scanner& sc, std::string& a) {a.clear();char c;if ((c = sc.scan_char()) == '\0' || c == '\n') return sc;a += c;while ((c = sc.scan_char()) != '\0' && c != '\n') a += c;return sc;}};Scanner<> sc;} // namespace fastiousing fastio::sc;#line 6 "library/template/out.hpp"namespace fastio {struct Pre {char buffer[10000][4];constexpr Pre() : buffer() {for (int i = 0; i < 10000; ++i) {int n = i;for (int j = 3; j >= 0; --j) {buffer[i][j] = n % 10 | '0';n /= 10;}}}} constexpr pre;template <std::size_t BUFF_SIZE = 1 << 17, bool debug = false>struct Printer {private:template <typename, bool = debug, class = void>struct has_print : std::false_type {};template <typename T>struct has_print<T, false, decltype(std::declval<T>().print(std::declval<Printer&>()), (void)0)> : std::true_type {};template <typename T>struct has_print<T, true, decltype(std::declval<T>().debug(std::declval<Printer&>()), (void)0)> : std::true_type {};int fd;char buffer[BUFF_SIZE];int idx;std::size_t decimal_precision;public:Printer() : Printer((debug ? 2 : 1)) {}explicit Printer(int fd) : fd(fd), idx(0), decimal_precision(16) {}explicit Printer(FILE* file) : fd(fileno(file)), idx(0), decimal_precision(16) {}~Printer() {flush();}void set_decimal_precision(std::size_t n) { decimal_precision = n; }inline void print_char(char c) {buffer[idx++] = c;if (idx == BUFF_SIZE) flush();}inline void flush() {idx = write(fd, buffer, idx);idx = 0;}void print(char a) {if constexpr (debug) print_char('\'');print_char(a);if constexpr (debug) print_char('\'');}void print(bool a) {if constexpr (debug) print_char('\'');print_char('0' + a);if constexpr (debug) print_char('\'');}void print(const char* a) {if constexpr (debug) print_char('\"');for (; *a != '\0'; ++a) print_char(*a);if constexpr (debug) print_char('\"');}template <std::size_t N>void print(const char (&a)[N]) {if constexpr (debug) print_char('\"');for (auto i : a) print_char(i);if constexpr (debug) print_char('\"');}void print(const std::string& a) {if constexpr (debug) print_char('\"');for (auto i : a) print_char(i);if constexpr (debug) print_char('\"');}template <std::size_t len>void print(const std::bitset<len>& a) {for (int i = len - 1; i >= 0; --i) print_char('0' + a[i]);}template <typename T, typename std::enable_if<is_int<T>::value && !has_print<T>::value>::type* = nullptr>void print(T a) {if (!a) {print_char('0');return;}if constexpr (is_signed_int<T>::value) {if (a < 0) {print_char('-');a = -a;}}if (static_cast<size_t>(idx + 40) >= BUFF_SIZE) flush();static char stk[40];int top = 40;while (a >= 10000) {int i = a % 10000;a /= 10000;top -= 4;std::memcpy(stk + top, pre.buffer[i], 4);}if (a >= 1000) {std::memcpy(buffer + idx, pre.buffer[a], 4);idx += 4;} else if (a >= 100) {std::memcpy(buffer + idx, pre.buffer[a] + 1, 3);idx += 3;} else if (a >= 10) {std::memcpy(buffer + idx, pre.buffer[a] + 2, 2);idx += 2;} else {buffer[idx++] = '0' | a;}std::memcpy(buffer + idx, stk + top, 40 - top);idx += 40 - top;}template <typename T, typename std::enable_if<std::is_floating_point<T>::value && !has_print<T>::value>::type* = nullptr>void print(T a) {if (a == infinity<T>::max || a == infinity<T>::value) {print("inf");return;}if (a == infinity<T>::min || a == infinity<T>::mvalue) {print("-inf");return;}if (std::isnan(a)) {print("nan");return;}if (a < 0) {print_char('-');a = -a;}T b = a;if (b < 1) {print_char('0');} else {std::string s;while (b >= 1) {s += (char)('0' | (int)std::fmod(b, 10.0));b /= 10;}for (auto i = s.rbegin(); i != s.rend(); ++i) {print_char(*i);}}print_char('.');for (std::size_t _ = 0; _ < decimal_precision; ++_) {a *= 10;print_char('0' | (int)std::fmod(a, 10.0));}}private:template <std::size_t i, typename... Args>void print(const std::tuple<Args...>& a) {if constexpr (i < sizeof...(Args)) {if constexpr (debug) print_char(',');print_char(' ');print(std::get<i>(a));print<i + 1>(a);}}public:template <typename... Args>void print(const std::tuple<Args...>& a) {if constexpr (debug) print_char('(');if constexpr (sizeof...(Args) != 0) {print(std::get<0>(a));}print<1, Args...>(a);if constexpr (debug) print_char(')');}template <typename T, typename U>void print(const std::pair<T, U>& a) {if constexpr (debug) print_char('(');print(a.first);if constexpr (debug) print_char(',');print_char(' ');print(a.second);if constexpr (debug) print_char(')');}template <typename T, typename std::enable_if<is_range<T>::value>::type* = nullptr>void print(const T& a) {if constexpr (debug) print_char('{');auto it = std::begin(a);if (it != std::end(a)) {print(*it);while (++it != std::end(a)) {if constexpr (debug) print_char(',');print_char(' ');print(*it);}}if constexpr (debug) print_char('}');}template <typename T, typename std::enable_if<has_print<T>::value && !debug>::type* = nullptr>void print(const T& a) {a.print(*this);}template <typename T, typename std::enable_if<has_print<T>::value && debug>::type* = nullptr>void print(const T& a) {a.debug(*this);}void operator()() {}template <typename Head, typename... Tail>void operator()(const Head& head, const Tail&... tail) {print(head);operator()(std::forward<const Tail&>(tail)...);}template <typename T>Printer& operator<<(const T& a) {print(a);return *this;}Printer& operator<<(Printer& (*f)(Printer&)) {return f(*this);}};template <std::size_t BUFF_SIZE, bool debug>Printer<BUFF_SIZE, debug>& endl(Printer<BUFF_SIZE, debug>& out) {out.print_char('\n');out.flush();return out;}template <std::size_t BUFF_SIZE, bool debug>Printer<BUFF_SIZE, debug>& flush(Printer<BUFF_SIZE, debug>& out) {out.flush();return out;}Printer<> pr;Printer<1 << 17, true> prd;} // namespace fastiousing fastio::endl;using fastio::flush;using fastio::pr;using fastio::prd;#line 3 "library/template/func.hpp"#line 8 "library/template/func.hpp"inline constexpr int msb(ull x) {int res = x ? 0 : -1;if (x & 0xffffffff00000000) x &= 0xffffffff00000000, res += 32;if (x & 0xffff0000ffff0000) x &= 0xffff0000ffff0000, res += 16;if (x & 0xff00ff00ff00ff00) x &= 0xff00ff00ff00ff00, res += 8;if (x & 0xf0f0f0f0f0f0f0f0) x &= 0xf0f0f0f0f0f0f0f0, res += 4;if (x & 0xcccccccccccccccc) x &= 0xcccccccccccccccc, res += 2;return res + (x & 0xaaaaaaaaaaaaaaaa ? 1 : 0);}inline constexpr int ceil_log2(ull x) { return x ? msb(x - 1) + 1 : 0; }inline constexpr ull reverse(ull x) {x = ((x & 0x5555555555555555) << 1) | ((x & 0xaaaaaaaaaaaaaaaa) >> 1);x = ((x & 0x3333333333333333) << 2) | ((x & 0xcccccccccccccccc) >> 2);x = ((x & 0x0f0f0f0f0f0f0f0f) << 4) | ((x & 0xf0f0f0f0f0f0f0f0) >> 4);x = ((x & 0x00ff00ff00ff00ff) << 8) | ((x & 0xff00ff00ff00ff00) >> 8);x = ((x & 0x0000ffff0000ffff) << 16) | ((x & 0xffff0000ffff0000) >> 16);return (x << 32) | (x >> 32);}inline constexpr ull reverse(ull x, int len) { return reverse(x) >> (64 - len); }inline constexpr int popcnt(ull x) {#if __cplusplus >= 202002Lreturn std::popcount(x);#endifx = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f);x = (x & 0x00ff00ff00ff00ff) + ((x >> 8) & 0x00ff00ff00ff00ff);x = (x & 0x0000ffff0000ffff) + ((x >> 16) & 0x0000ffff0000ffff);return (x & 0x00000000ffffffff) + ((x >> 32) & 0x00000000ffffffff);}template <typename T, typename U>inline constexpr bool chmin(T& a, U b) { return a > b && (a = b, true); }template <typename T, typename U>inline constexpr bool chmax(T& a, U b) { return a < b && (a = b, true); }inline constexpr ll gcd(ll a, ll b) {if (a < 0) a = -a;if (b < 0) b = -b;while (b) {const ll c = b;b = a % b;a = c;}return a;}inline constexpr ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }inline constexpr bool is_prime(ll n) {if (n <= 1) return false;for (ll i = 2; i * i <= n; i++) {if (n % i == 0) return false;}return true;}inline constexpr ll my_pow(ll a, ll b) {ll res = 1;while (b) {if (b & 1) res *= a;a *= a;b >>= 1;}return res;}inline constexpr ll mod_pow(ll a, ll b, const ll& mod) {if (mod == 1) return 0;a %= mod;ll res = 1;while (b) {if (b & 1) (res *= a) %= mod;(a *= a) %= mod;b >>= 1;}return res;}inline ll mod_inv(ll a, const ll& mod) {ll b = mod, x = 1, u = 0, t;while (b) {t = a / b;std::swap(a -= t * b, b);std::swap(x -= t * u, u);}if (x < 0) x += mod;return x;}template <typename T>T binary_gcd(T x_, T y_) {T x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;if (!x || !y) return x + y;int n = __builtin_ctzll(x), m = __builtin_ctzll(y);x >>= n, y >>= m;while (x != y) {if (x > y) {x = (x - y) >> __builtin_ctzll(x - y);} else {y = (y - x) >> __builtin_ctzll(y - x);}}return x << std::min(n, m);}template <typename T, typename U>std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {os << p.first << " " << p.second;return os;}template <typename T, typename U>std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {is >> p.first >> p.second;return is;}template <typename T>std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {for (auto it = std::begin(v); it != std::end(v);) {os << *it << ((++it) != std::end(v) ? " " : "");}return os;}template <typename T>std::istream& operator>>(std::istream& is, std::vector<T>& v) {for (T& in : v) {is >> in;}return is;}inline void scan() {}template <class Head, class... Tail>inline void scan(Head& head, Tail&... tail) {sc >> head;scan(tail...);}template <class T>inline void print(const T& t) { pr << t << '\n'; }template <class Head, class... Tail>inline void print(const Head& head, const Tail&... tail) {pr << head << ' ';print(tail...);}template <class... T>inline void fin(const T&... a) {print(a...);exit(0);}template <typename T>inline void dump(const T& a) { prd << a; }inline void trace() { prd << endl; }template <typename Head, typename... Tail>inline void trace(const Head& head, const Tail&... tail) {dump(head);if (sizeof...(tail)) prd.print_char(','), prd.print_char(' ');trace(tail...);}#ifdef ONLINE_JUDGE#define dbg(...) (void(0))#else#define dbg(...) \do { \prd << #__VA_ARGS__; \prd.print_char(' '), prd.print_char('='), prd.print_char(' '); \trace(__VA_ARGS__); \} while (0)#endif#line 3 "library/template/util.hpp"#line 6 "library/template/util.hpp"template <typename F>struct REC {private:F f;public:explicit constexpr REC(F&& f_) : f(std::forward<F>(f_)) {}template <typename... Args>constexpr auto operator()(Args&&... args) const {return f(*this, std::forward<Args>(args)...);}};template <typename T, typename Comp = std::less<T>>struct compressor {private:std::vector<T> data;Comp cmp;bool sorted = false;public:compressor() : compressor(Comp()) {}compressor(const Comp& cmp) : cmp(cmp) {}compressor(const std::vector<T>& dat, const Comp& cmp = Comp()) : data(dat), cmp(cmp) {}compressor(std::vector<T>&& dat, const Comp& cmp = Comp()) : data(std::move(dat)), cmp(cmp) {}compressor(std::initializer_list<T> li, const Comp& cmp = Comp()) : data(li.begin(), li.end()), cmp(cmp) {}void push_back(const T& v) {assert(!sorted);data.push_back(v);}void push_back(T&& v) {assert(!sorted);data.push_back(std::move(v));}template <typename... Args>void emplace_back(Args&&... args) {assert(!sorted);data.emplace_back(std::forward<Args>(args)...);}void push(const std::vector<T>& v) {assert(!sorted);const int n = data.size();data.resize(v.size() + n);for (int i = 0; i < (int)v.size(); i++) data[i + n] = v[i];}void build() {assert(!sorted);sorted = 1;std::sort(data.begin(), data.end(), cmp);data.erase(unique(data.begin(), data.end(), [&](const T& l, const T& r) -> bool { return !cmp(l, r) && !cmp(r, l); }), data.end());}const T& operator[](int k) const& {assert(sorted);return data[k];}int get_index(const T& v) const {assert(sorted);return int(lower_bound(data.begin(), data.end(), v, cmp) - data.begin());}void press(std::vector<T>& v) const {assert(sorted);for (auto&& i : v) i = get_index(i);}std::vector<int> pressed(const std::vector<T>& v) const {assert(sorted);std::vector<int> ret(v.size());for (int i = 0; i < (int)v.size(); i++) ret[i] = get_index(v[i]);return ret;}int size() const {assert(sorted);return data.size();}};#line 11 "library/template/template.hpp"using namespace std;#line 3 "library/math/modular/modint.hpp"namespace internal {struct modint_base {};} // namespace internaltemplate <typename T>using is_modint = is_base_of<internal::modint_base, T>;template <typename T, T mod>struct StaticModInt : internal::modint_base {static_assert(is_integral<T>::value, "T must be integral");static_assert(is_unsigned<T>::value, "T must be unsgined");static_assert(mod > 0, "mod must be positive");static_assert(mod <= INF<T>, "mod*2 must be less than or equal to T::max()");private:using large_t = typename double_size_uint<T>::type;using signed_t = typename make_signed<T>::type;T val;public:constexpr StaticModInt() : val(0) {}template <typename U, typename enable_if<is_integral<U>::value && is_unsigned<U>::value>::type* = nullptr>constexpr StaticModInt(U x) : val(x % mod) {}template <typename U, typename enable_if<is_integral<U>::value && is_signed<U>::value>::type* = nullptr>constexpr StaticModInt(U x) : val{} {x %= static_cast<signed_t>(mod);if (x < 0) x += static_cast<signed_t>(mod);val = static_cast<T>(x);}constexpr T get() const { return val; }static constexpr T get_mod() { return mod; }static constexpr StaticModInt raw(T v) {StaticModInt res;res.val = v;return res;}constexpr StaticModInt inv() const {return mod_inv(val, mod);}constexpr StaticModInt& operator++() {++val;if (val == mod) val = 0;return *this;}constexpr StaticModInt operator++(int) {StaticModInt res = *this;++*this;return res;}constexpr StaticModInt& operator--() {if (val == 0) val = mod;--val;return *this;}constexpr StaticModInt operator--(int) {StaticModInt res = *this;--*this;return res;}constexpr StaticModInt& operator+=(const StaticModInt& x) {val += x.val;if (val >= mod) val -= mod;return *this;}constexpr StaticModInt& operator-=(const StaticModInt& x) {if (val < x.val) val += mod;val -= x.val;return *this;}constexpr StaticModInt& operator*=(const StaticModInt& x) {val = static_cast<T>((static_cast<large_t>(val) * x.val) % mod);return *this;}constexpr StaticModInt& operator/=(const StaticModInt& x) {return *this *= x.inv();}friend constexpr StaticModInt operator+(const StaticModInt& l, const StaticModInt& r) { return StaticModInt(l) += r; }friend constexpr StaticModInt operator-(const StaticModInt& l, const StaticModInt& r) { return StaticModInt(l) -= r; }friend constexpr StaticModInt operator*(const StaticModInt& l, const StaticModInt& r) { return StaticModInt(l) *= r; }friend constexpr StaticModInt operator/(const StaticModInt& l, const StaticModInt& r) { return StaticModInt(l) /= r; }constexpr StaticModInt operator+() const { return StaticModInt(*this); }constexpr StaticModInt operator-() const { return StaticModInt() - *this; }friend constexpr bool operator==(const StaticModInt& l, const StaticModInt& r) { return l.val == r.val; }friend constexpr bool operator!=(const StaticModInt& l, const StaticModInt& r) { return l.val != r.val; }constexpr StaticModInt pow(ll a) const {StaticModInt v = *this, res = 1;if (a < 0) {a = -a;v = v.inv();}while (a) {if (a & 1) res *= v;v *= v;a >>= 1;}return res;}template <typename Sc>void scan(Sc& a) {ll x;a.scan(x);*this = x;}template <typename Pr>void print(Pr& a) const {a.print(val);}template <typename Pr>void debug(Pr& a) const {a.print(val);}};template <unsigned int p>using ModInt = StaticModInt<unsigned int, p>;template <typename T, int id>struct DynamicModInt {static_assert(is_integral<T>::value, "T must be integral");static_assert(is_unsigned<T>::value, "T must be unsigned");private:using large_t = typename double_size_uint<T>::type;using signed_t = typename make_signed<T>::type;T val;static T mod;public:constexpr DynamicModInt() : val(0) {}template <typename U, typename enable_if<is_integral<U>::value && is_unsigned<U>::value>::type* = nullptr>constexpr DynamicModInt(U x) : val(x % mod) {}template <typename U, typename enable_if<is_integral<U>::value && is_signed<U>::value>::type* = nullptr>constexpr DynamicModInt(U x) : val{} {x %= static_cast<signed_t>(mod);if (x < 0) x += static_cast<signed_t>(mod);val = static_cast<T>(x);}T get() const { return val; }static T get_mod() { return mod; }static void set_mod(T x) {mod = x;assert(mod > 0);assert(mod <= INF<T>);}static DynamicModInt raw(T v) {DynamicModInt res;res.val = v;return res;}DynamicModInt inv() const {return mod_inv(val, mod);}DynamicModInt& operator++() {++val;if (val == mod) val = 0;return *this;}DynamicModInt operator++(int) {DynamicModInt res = *this;++*this;return res;}DynamicModInt& operator--() {if (val == 0) val = mod;--val;return *this;}DynamicModInt operator--(int) {DynamicModInt res = *this;--*this;return res;}DynamicModInt& operator+=(const DynamicModInt& x) {val += x.val;if (val >= mod) val -= mod;return *this;}DynamicModInt& operator-=(const DynamicModInt& x) {if (val < x.val) val += mod;val -= x.val;return *this;}DynamicModInt& operator*=(const DynamicModInt& x) {val = static_cast<T>((static_cast<large_t>(val) * x.val) % mod);return *this;}DynamicModInt& operator/=(const DynamicModInt& x) {return *this *= x.inv();}friend DynamicModInt operator+(const DynamicModInt& l, const DynamicModInt& r) { return DynamicModInt(l) += r; }friend DynamicModInt operator-(const DynamicModInt& l, const DynamicModInt& r) { return DynamicModInt(l) -= r; }friend DynamicModInt operator*(const DynamicModInt& l, const DynamicModInt& r) { return DynamicModInt(l) *= r; }friend DynamicModInt operator/(const DynamicModInt& l, const DynamicModInt& r) { return DynamicModInt(l) /= r; }DynamicModInt operator+() const { return DynamicModInt(*this); }DynamicModInt operator-() const { return DynamicModInt() - *this; }friend bool operator==(const DynamicModInt& l, const DynamicModInt& r) { return l.val == r.val; }friend bool operator!=(const DynamicModInt& l, const DynamicModInt& r) { return l.val != r.val; }DynamicModInt pow(ll a) const {DynamicModInt v = *this, res = 1;if (a < 0) {a = -a;v = v.inv();}while (a) {if (a & 1) res *= v;v *= v;a >>= 1;}return res;}template <typename Sc>void scan(Sc& a) {ll x;a.scan(x);*this = x;}template <typename Pr>void print(Pr& a) const {a.print(val);}template <typename Pr>void debug(Pr& a) const {a.print(val);}};template <typename T, int id>T DynamicModInt<T, id>::mod = 998244353;template <int id>using dynamic_modint = DynamicModInt<unsigned int, id>;using modint = dynamic_modint<-1>;/*** @brief ModInt*/#line 4 "library/math/others/combinatorics.hpp"template <typename T>struct Combinatorics {private:static vector<T> dat, idat;public:static void extend(int sz) {const int pre_sz = dat.size();if (sz < pre_sz) return;dat.resize(sz + 1, 1);idat.resize(sz + 1, 1);for (int i = pre_sz; i <= sz; i++) dat[i] = dat[i - 1] * i;idat[sz] = T(1) / dat[sz];for (int i = sz - 1; i >= pre_sz; i--) idat[i] = idat[i + 1] * (i + 1);}static T fac(ll n) {if (n < 0) return T();extend(n);return dat[n];}static T finv(ll n) {if (n < 0) return T();extend(n);return idat[n];}static T inv(ll n) {if (n <= 0) return T();extend(n);return dat[n - 1] * idat[n];}static T com(ll n, ll k) {if (k < 0 || n < k || n < 0) return T();extend(n);return dat[n] * idat[k] * idat[n - k];}static T hom(ll n, ll k) {if (n < 0 || k < 0) return T();return k == 0 ? 1 : com(n + k - 1, k);}static inline T per(ll n, ll k) {if (k < 0 || n < k) return T();extend(n);return dat[n] * idat[n - k];}};template <typename T>vector<T> Combinatorics<T>::dat = vector<T>(2, 1);template <typename T>vector<T> Combinatorics<T>::idat = vector<T>(2, 1);template <long long p>struct COMB {private:static vector<vector<ModInt<p>>> comb;static void init() {if (!comb.empty()) return;comb.assign(p, vector<ModInt<p>>(p));comb[0][0] = 1;for (int i = 1; i < p; i++) {comb[i][0] = 1;for (int j = i; j > 0; j--) comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];}}public:COMB() {init();}ModInt<p> com(int n, int k) {init();ModInt<p> ret = 1;while (n > 0 || k > 0) {int ni = n % p, ki = k % p;ret *= comb[ni][ki];n /= p;k /= p;}return ret;}};template <long long p>vector<vector<ModInt<p>>> COMB<p>::comb = vector<vector<ModInt<p>>>();/*** @brief Combinatorics(組み合わせ)*/#line 4 "code.cpp"using mint = ModInt<998244353>;Combinatorics<mint> comb;int main() {LL(n);if (n & 1) fin(0);n /= 2;n--;print(mint(2).pow(2 * n + 1) - comb.com(2 * n + 3, n + 1) + comb.com(2 * n + 1, n));return 0;/*rep(n, 1, 11) {ll sum = 0;rep(bit, 1 << (2 * n)) {stack<ll> st;ll ans = 0;bool f = true;rep(i, 2 * n) {if ((bit >> i) & 1) {st.emplace(i);} else {if (st.empty()) {f = false;break;}st.pop();ans += st.size();}}f &= st.empty();if (f) sum += ans;}print(sum);}*/}