QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #41421 | #1085. Brave Seekers of Unicorns | antiravel | AC ✓ | 48ms | 11092kb | C++23 | 17.3kb | 2022-07-30 15:12:51 | 2022-07-30 15:12:52 |
Judging History
answer
#include <algorithm>
#include <bitset>
#include <cinttypes>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace impl
{
inline void force_templates()
{
#define FORCE(type) \
{ \
[[maybe_unused]] auto f = [] type {}; \
}
FORCE((std::pair<int, int>))
FORCE((std::vector<int>))
FORCE((std::vector<std::pair<int, int>>))
#undef FORCE
}
} // namespace impl
#include <iostream>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>
namespace cm
{
class logger
{
public:
logger(std::ostream &) {}
logger &set_ostream(std::ostream &)
{
return *this;
}
logger &set_sep(const std::string &)
{
return *this;
}
logger &assert_push_enable()
{
return *this;
}
logger &assert_push_disable()
{
return *this;
}
logger &assert_exit()
{
return *this;
}
logger &assert_noexit()
{
return *this;
}
logger &endl()
{
return *this;
}
template <class... T>
logger &log(T...)
{
return *this;
}
template <class T>
logger &hint(T...)
{
return *this;
}
template <class... T>
logger &operator()(T...)
{
return *this;
}
template <class... T>
logger &assert_(T...)
{
return *this;
}
};
namespace impl
{
logger cm_logger(std::cout);
}
} // namespace cm
// clang-format off
#define see(...)
#define asee(...)
#define cm_assert(...)
// clang-format on
#if __cplusplus >= 201103L
#include <type_traits>
#endif
#include <iostream>
#include <limits>
#define INTM_FAST_32 int
#define INTM_FAST_64 unsigned long long
#define _ATTR_INLINE __attribute__((always_inline)) inline
#if __cplusplus >= 201103L
#define _CXX11_CONSTEXPR constexpr
#define CXX11_EXPLICIT explicit
#else
#define _CXX11_CONSTEXPR
#define CXX11_EXPLICIT
#endif
#if __cplusplus >= 201402L
#define _CXX14_CONSTEXPR constexpr
#else
#define _CXX14_CONSTEXPR
#endif
namespace cm
{
template <INTM_FAST_32 _MOD = 998244353>
class intm
{
#if __cplusplus >= 201103L
static_assert(_MOD * 2 < std::numeric_limits<INTM_FAST_32>::max(), "");
#endif
public:
static constexpr int MOD = _MOD;
protected:
INTM_FAST_32 a = 0;
_ATTR_INLINE _CXX11_CONSTEXPR explicit intm(INTM_FAST_32 a, int) : a(a) {}
static _ATTR_INLINE _CXX11_CONSTEXPR INTM_FAST_32 __impl_inc(INTM_FAST_32 a)
{
return a < 0 ? a + MOD : a;
}
static _ATTR_INLINE _CXX11_CONSTEXPR INTM_FAST_32 __impl_dec(INTM_FAST_32 a)
{
return a >= MOD ? a - MOD : a;
}
template <class IntType>
static _ATTR_INLINE _CXX14_CONSTEXPR INTM_FAST_32 __impl_pow(INTM_FAST_32 a,
IntType b)
{
INTM_FAST_32 res = 1;
for (; b; b >>= 1)
{
if (b & 1)
{
res = (INTM_FAST_32)((INTM_FAST_64)(res) * (INTM_FAST_64)(a) % MOD);
}
a = (INTM_FAST_32)((INTM_FAST_64)(a) * (INTM_FAST_64)(a) % MOD);
}
return res;
}
static int pretty(int x)
{
if (x >= MOD - 1000)
return x - MOD;
return x;
}
public:
#if __cplusplus >= 201103L
intm() = default;
#else
intm() {}
#endif
static _CXX11_CONSTEXPR intm raw(INTM_FAST_32 x)
{
return intm(x, 0);
}
// clang-format off
_ATTR_INLINE _CXX11_CONSTEXPR intm(int a) : a(static_cast<INTM_FAST_32>(__impl_inc(a % MOD))) {}
_ATTR_INLINE _CXX11_CONSTEXPR intm(long a) : a(static_cast<INTM_FAST_32>(__impl_inc(a % MOD))) {}
_ATTR_INLINE _CXX11_CONSTEXPR intm(long long a) : a(static_cast<INTM_FAST_32>(__impl_inc(a % MOD))) {}
_ATTR_INLINE _CXX11_CONSTEXPR intm(unsigned int a) : a(static_cast<INTM_FAST_32>(a % MOD)) {}
_ATTR_INLINE _CXX11_CONSTEXPR intm(unsigned long a) : a(static_cast<INTM_FAST_32>(a % MOD)) {}
_ATTR_INLINE _CXX11_CONSTEXPR intm(unsigned long long a) : a(static_cast<INTM_FAST_32>(a % MOD)) {}
// clang-format on
template <class _IntType>
_ATTR_INLINE _CXX11_CONSTEXPR CXX11_EXPLICIT operator _IntType() const
{
return a;
}
_ATTR_INLINE friend std::ostream &operator<<(std::ostream &out,
const intm rhs)
{
out << rhs.a;
return out;
}
_ATTR_INLINE friend std::istream &operator>>(std::istream &in, intm &rhs)
{
long long a;
in >> a;
rhs = intm(a);
return in;
}
template <class _IntType>
_ATTR_INLINE _CXX14_CONSTEXPR intm pow(_IntType k) const
{
return raw(__impl_pow(a, k));
}
_ATTR_INLINE _CXX14_CONSTEXPR intm inv() const
{
cm_assert(a != 0, "warning: 0 do not have inv");
return raw(__impl_pow(a, MOD - 2));
}
// clang-format off
_ATTR_INLINE _CXX11_CONSTEXPR friend bool operator< (const intm a, const intm b) { return a.a < b.a; }
_ATTR_INLINE _CXX11_CONSTEXPR friend bool operator<= (const intm a, const intm b) { return a.a <= b.a; }
_ATTR_INLINE _CXX11_CONSTEXPR friend bool operator> (const intm a, const intm b) { return a.a > b.a; }
_ATTR_INLINE _CXX11_CONSTEXPR friend bool operator>= (const intm a, const intm b) { return a.a >= b.a; }
_ATTR_INLINE _CXX11_CONSTEXPR friend bool operator== (const intm a, const intm b) { return a.a == b.a; }
_ATTR_INLINE _CXX11_CONSTEXPR friend bool operator!= (const intm a, const intm b) { return a.a != b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator< (const _IntType a, const intm b) { return a < b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator< (const intm a, const _IntType b) { return a.a < b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator<= (const _IntType a, const intm b) { return a <= b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator<= (const intm a, const _IntType b) { return a.a <= b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator> (const _IntType a, const intm b) { return a > b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator> (const intm a, const _IntType b) { return a.a > b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator>= (const _IntType a, const intm b) { return a >= b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator>= (const intm a, const _IntType b) { return a.a >= b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator== (const _IntType a, const intm b) { return a == b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator== (const intm a, const _IntType b) { return a.a == b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator!= (const _IntType a, const intm b) { return a != b.a; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend bool operator!= (const intm a, const _IntType b) { return a.a != b; }
_ATTR_INLINE _CXX11_CONSTEXPR friend intm operator+ (const intm a, const intm b) { return raw(__impl_dec(a.a + b.a)); }
_ATTR_INLINE _CXX11_CONSTEXPR friend intm operator- (const intm a, const intm b) { return raw(__impl_inc(a.a - b.a)); }
_ATTR_INLINE _CXX11_CONSTEXPR friend intm operator* (const intm a, const intm b) { return raw(static_cast<INTM_FAST_32>((INTM_FAST_64)(a.a) * (INTM_FAST_64)(b.a) % MOD)); }
_ATTR_INLINE _CXX14_CONSTEXPR friend intm operator/ (const intm a, const intm b) { return a * b.inv(); }
_ATTR_INLINE _CXX11_CONSTEXPR friend intm& operator+= ( intm &a, const intm b) { return a = a + b; }
_ATTR_INLINE _CXX11_CONSTEXPR friend intm& operator-= ( intm &a, const intm b) { return a = a - b; }
_ATTR_INLINE _CXX11_CONSTEXPR friend intm& operator*= ( intm &a, const intm b) { return a = a * b; }
_ATTR_INLINE _CXX14_CONSTEXPR friend intm& operator/= ( intm &a, const intm b) { return a = a / b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm operator+ (const intm a, const _IntType b) { return a + intm(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm operator- (const intm a, const _IntType b) { return a - intm(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm operator* (const intm a, const _IntType b) { return a * intm(b); }
template <class _IntType> _ATTR_INLINE _CXX14_CONSTEXPR friend intm operator/ (const intm a, const _IntType b) { return a / intm(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm& operator+= ( intm &a, const _IntType b) { return a += intm(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm& operator-= ( intm &a, const _IntType b) { return a -= intm(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm& operator*= ( intm &a, const _IntType b) { return a *= intm(b); }
template <class _IntType> _ATTR_INLINE _CXX14_CONSTEXPR friend intm& operator/= ( intm &a, const _IntType b) { return a /= intm(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm operator+ (const _IntType a, const intm b) { return intm(a) + b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm operator- (const _IntType a, const intm b) { return intm(a) - b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend intm operator* (const _IntType a, const intm b) { return intm(a) * b; }
template <class _IntType> _ATTR_INLINE _CXX14_CONSTEXPR friend intm operator/ (const _IntType a, const intm b) { return intm(a) / b; }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend _IntType& operator+= ( _IntType &a, const intm b) { return a += _IntType(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend _IntType& operator-= ( _IntType &a, const intm b) { return a -= _IntType(b); }
template <class _IntType> _ATTR_INLINE _CXX11_CONSTEXPR friend _IntType& operator*= ( _IntType &a, const intm b) { return a *= _IntType(b); }
template <class _IntType> _ATTR_INLINE _CXX14_CONSTEXPR friend _IntType& operator/= ( _IntType &a, const intm b) { return a /= _IntType(b); }
// clang-format on
};
} // namespace cm
#undef _ATTR_INLINE
#undef _CXX11_CONSTEXPR
#undef _CXX14_CONSTEXPR
#undef INTM_FAST_32
#undef INTM_FAST_64
// #include "/home/jack/cm/math_util.hpp"
#include <cctype>
#include <cstdio>
namespace cm
{
template <class _Type, size_t _buf_size>
class buffer_reader
{
protected:
FILE *src;
_Type *const buff;
_Type *buff_end;
_Type *buff_pos;
void _flush()
{
buff_end = buff + fread(buff, sizeof(_Type), _buf_size, src);
buff_pos = buff;
if (buff_end == buff)
{
*buff_end = '\n';
buff_end++;
}
}
public:
explicit buffer_reader(FILE *_src) : src(_src), buff(new _Type[_buf_size])
{
_flush();
}
buffer_reader(const buffer_reader &) = delete;
buffer_reader(buffer_reader &&) = delete;
buffer_reader &operator=(const buffer_reader &) = delete;
buffer_reader &operator=(buffer_reader &&) = delete;
_Type get() const
{
return *buff_pos;
}
_Type next()
{
_Type result = get();
buff_pos++;
if (buff_pos == buff_end)
_flush();
return result;
}
~buffer_reader()
{
if (src != stdin)
fclose(src);
delete[] buff;
}
};
template <class _BufferReader>
class scanner : protected _BufferReader
{
private:
using _BufferReader::get;
using _BufferReader::next;
inline bool _is_ws(char c)
{
return c <= ' ';
}
inline bool _is_cr(char c)
{
return c == '\n' || c == '\r';
}
int _get_sign()
{
while (!isdigit(get()) && get() != '-')
next();
if (get() == '-')
return next(), -1;
return 1;
}
public:
scanner() = delete;
using _BufferReader::_BufferReader;
char next_char()
{
while (_is_ws(get()))
next();
return next();
}
char *next_token(char *s)
{
while (_is_ws(get()))
next();
while (!_is_ws(get()))
*s++ = next();
*s = '\0';
return s;
}
char *next_line(char *s)
{
while (_is_ws(get()))
next();
while (!_is_cr(get()))
*s++ = next();
*s = '\0';
return s;
}
template <class _Integer>
_Integer next_integer()
{
_Integer sign = _get_sign();
_Integer result(0);
while (isdigit(get()))
result = result * _Integer(10) + _Integer(next() - '0');
return sign * result;
}
int next_int()
{
return next_integer<int>();
}
long long next_long()
{
return next_integer<long long>();
}
double next_double()
{
int sign = _get_sign();
double result = 0;
while (isdigit(get()))
result = result * 10 + (next() - '0');
if (get() == '.')
{
next();
double cur_ep = 0.1;
while (isdigit(get()))
result += cur_ep * (next() - '0'), cur_ep *= 0.1;
}
return sign * result;
}
};
} // namespace cm
namespace cm
{
using optimal_reader = buffer_reader<char, 1 << 16>;
}
#define DEFINE_SCANNER(sc, filename) \
cm::scanner<cm::optimal_reader> sc(fopen(filename, "r"));
// #include "/home/jack/cm/segment_tree.hpp"
// #include "/home/jack/cm/string.hpp"
#include <array>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>
namespace cm
{
template <class T>
inline bool check_min(T &a, const T &b)
{
return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool check_max(T &a, const T &b)
{
return a < b ? a = b, 1 : 0;
}
struct once_t
{
bool _once = true;
bool operator()()
{
return _once ? (_once = false, true) : false;
}
};
template <class T, class vt = std::vector<std::vector<T>>>
vt vec_transpose(const vt &v)
{
size_t n = v.size();
size_t m = v[0].size();
vt r(m, std::vector<T>(n));
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j < m; j++)
r[j][i] = v[i][j];
return r;
}
template <class value_type = int>
struct counter_t
{
private:
value_type _value{};
public:
value_type operator()()
{
return _value++;
}
value_type size() const
{
return _value;
}
void clear()
{
_value = value_type{};
}
};
namespace impl
{
template <class T, std::size_t n0, std::size_t... n1>
struct __array
{
using type = std::array<typename __array<T, n1...>::type, n0>;
};
template <class T, std::size_t n0>
struct __array<T, n0>
{
using type = std::array<T, n0>;
};
} // namespace impl
template <class T, std::size_t... n0>
using array = typename impl::__array<T, n0...>::type;
#if __cplusplus >= 201402L
template <class F>
struct y_combinate_t
{
F f;
template <class... Args>
decltype(auto) operator()(Args &&...args) const
{
return f(*this, std::forward<Args>(args)...);
}
};
template <class F>
y_combinate_t<std::decay_t<F>> y_combinate(F &&f)
{
return {std::forward<F>(f)};
};
auto vec_take(size_t id)
{
return [id](const auto &v) { return v[id]; };
}
template <class F, class... T>
auto vec_map(F &&f, const std::vector<T> &...v)
{
using mapped_t = decltype(f(std::declval<T>()...));
std::size_t n = [](auto x, auto...) { return x; }(v.size()...);
std::vector<mapped_t> r;
r.reserve(n);
cm::y_combinate([&](auto &&self, std::size_t cnt, auto... its) -> void {
if (cnt > 0)
{
r.emplace_back(f((*its)...));
self(cnt - 1, std::next(its)...);
}
})(n, v.begin()...);
return r;
}
template <class F>
auto mapper(F &&f)
{
return [f](auto v) { return vec_map(f, v); };
}
template <class T>
auto transfer(T &&v)
{
return std::forward<T>(v);
}
template <class T, class F0, class... F1>
auto transfer(T &&v, F0 &&f0, F1 &&...f1)
{
return transfer(f0(std::forward<T>(v)), f1...);
}
#endif
} // namespace cm
using cm::check_max;
using cm::check_min;
#define CONSTRAINT(n, a, b) constexpr auto n = a;
#include <vector>
cm::scanner<cm::optimal_reader> sc(stdin);
int main()
{
constexpr int MOD = 998'244'353;
using int_t = cm::intm<MOD>;
int n = sc.next_int();
std::vector<int_t> a(n + 1);
std::vector<int_t> pa(n + 2);
a[0] = 1;
a[1] = 1;
pa[0] = 0;
pa[1] = 1;
pa[2] = 2;
for (int i = 2; i <= n; i++)
{
a[i] = pa[i];
int pw = 31 - __builtin_clz(i);
for (int j = pw - 1; j >= 0; j--)
if (i & (1 << j))
a[i] -= pa[1 << (j + 1)] - pa[1 << j];
pa[i + 1] = pa[i] + a[i];
}
std::cout << pa[n + 1] - 1 << std::endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3544kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
5
output:
26
result:
ok 1 number(s): "26"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
322
output:
782852421
result:
ok 1 number(s): "782852421"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
10
output:
728
result:
ok 1 number(s): "728"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
100
output:
234222727
result:
ok 1 number(s): "234222727"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
10000
output:
348787098
result:
ok 1 number(s): "348787098"
Test #9:
score: 0
Accepted
time: 48ms
memory: 10764kb
input:
1000000
output:
246427510
result:
ok 1 number(s): "246427510"
Test #10:
score: 0
Accepted
time: 45ms
memory: 11024kb
input:
999999
output:
525546416
result:
ok 1 number(s): "525546416"
Test #11:
score: 0
Accepted
time: 46ms
memory: 10584kb
input:
950000
output:
154241852
result:
ok 1 number(s): "154241852"
Test #12:
score: 0
Accepted
time: 42ms
memory: 11092kb
input:
999888
output:
254589934
result:
ok 1 number(s): "254589934"
Test #13:
score: 0
Accepted
time: 46ms
memory: 10996kb
input:
999423
output:
917909701
result:
ok 1 number(s): "917909701"
Test #14:
score: 0
Accepted
time: 27ms
memory: 7912kb
input:
600000
output:
546076071
result:
ok 1 number(s): "546076071"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1337
output:
616951443
result:
ok 1 number(s): "616951443"