結果

問題 No.2625 Bouns Ai
ユーザー AC2KAC2K
提出日時 2024-02-09 22:14:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 11,327 bytes
コンパイル時間 2,545 ms
コンパイル使用メモリ 250,732 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-28 15:30:13
合計ジャッジ時間 4,991 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "Library/src/debug.hpp"
#ifdef ONLINE_JUDGE
#define debug(x) void(0)
#else
#define _GLIBCXX_DEBUG
#define debug(x) std::cout << __LINE__ << " : " << #x << " = " << (x) << std::endl
#endif
#line 2 "Library/src/math/static_modint.hpp"
#include <cassert>
#include <cstdint>
#include <iostream>
#line 3 "Library/src/internal/type_traits.hpp"
#include <limits>
#include <numeric>
#include <typeinfo>
#line 7 "Library/src/internal/type_traits.hpp"
namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
: first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
using type = T;
};
template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
std::enable_if<dgt <= 16, std::int16_t>,
std::enable_if<dgt <= 32, std::int32_t>,
std::enable_if<dgt <= 64, std::int64_t>,
std::enable_if<dgt <= 128, __int128_t>>;
};
template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
std::enable_if<dgt <= 16, std::uint16_t>,
std::enable_if<dgt <= 32, std::uint32_t>,
std::enable_if<dgt <= 64, std::uint64_t>,
std::enable_if<dgt <= 128, __uint128_t>>;
};
template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;
template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;
template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;
struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
// is_integral
template <typename T>
using is_integral_t =
std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
std::is_same_v<T, __uint128_t>>;
}; // namespace internal
}; // namespace kyopro
/*
* @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
*/
#line 3 "Library/src/math/gcd.hpp"
#include <tuple>
namespace kyopro {
template <typename T> constexpr inline T _gcd(T a, T b) noexcept {
assert(a >= 0 && b >= 0);
if (a == 0 || b == 0) return a + b;
int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));
a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);
while (a != b) {
if (!a || !b) {
return a + b;
}
if (a >= b) {
a -= b;
a >>= __builtin_ctzll(a);
} else {
b -= a;
b >>= __builtin_ctzll(b);
}
}
return a << d;
}
template <typename T> constexpr inline T ext_gcd(T a, T b, T& x, T& y) noexcept {
x = 1, y = 0;
T nx = 0, ny = 1;
while (b) {
T q = a / b;
std::tie(a, b) = std::pair<T, T>{b, a % b};
std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
}
return a;
}
}; // namespace kyopro
#line 8 "Library/src/math/static_modint.hpp"
namespace kyopro {
template <int _mod, std::enable_if_t<_mod >= 0>* = nullptr>
class modint : internal::modint_base {
using mint = modint<_mod>;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
u32 v;
constexpr u32 normalize(i64 v_) const noexcept {
v_ %= _mod;
if (v_ < 0) {
v_ += _mod;
}
return v_;
}
public:
static constexpr u32 mod() noexcept { return _mod; }
constexpr modint() noexcept : v(0) {}
constexpr modint(i64 v_) noexcept : v(normalize(v_)) {}
static mint raw(u32 a) {
mint m;
m.v = a;
return m;
}
constexpr u32 val() const noexcept { return v; }
constexpr mint& operator+=(const mint& rhs) noexcept {
v += rhs.val();
if (v >= _mod) {
v -= _mod;
}
return (*this);
}
constexpr mint& operator-=(const mint& rhs) noexcept {
v += _mod - rhs.val();
if (v >= _mod) {
v -= _mod;
}
return (*this);
}
constexpr mint& operator*=(const mint& rhs) noexcept {
v = (u64)v * rhs.val() % _mod;
return (*this);
}
constexpr mint operator+(const mint& r) const noexcept {
return mint(*this) += r;
}
constexpr mint operator-(const mint& r) const noexcept {
return mint(*this) -= r;
}
constexpr mint operator*(const mint& r) const noexcept {
return mint(*this) *= r;
}
constexpr mint& operator+=(i64 rhs) noexcept {
(*this) += mint(rhs);
return (*this);
}
constexpr mint& operator-=(i64 rhs) noexcept {
(*this) -= mint(rhs);
return (*this);
}
constexpr mint& operator*=(i64 rhs) noexcept {
(*this) *= mint(rhs);
return (*this);
}
constexpr friend mint operator+(i64 l, const mint& r) noexcept {
return mint(l) += r;
}
constexpr friend mint operator-(i64 l, const mint& r) noexcept {
return mint(l) -= r;
}
constexpr friend mint operator*(i64 l, const mint& r) noexcept {
return mint(l) *= r;
}
constexpr mint operator+(i64 r) const noexcept { return mint(*this) += r; }
constexpr mint operator-(i64 r) const noexcept { return mint(*this) -= r; }
constexpr mint operator*(i64 r) const noexcept { return mint(*this) *= r; }
constexpr mint& operator=(i64 r) noexcept { return (*this) = mint(r); }
constexpr bool operator==(const mint& r) const noexcept {
return (*this).val() == r.val();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
constexpr mint pow(T e) const noexcept {
mint ans(1), base(*this);
while (e) {
if (e & 1) {
ans *= base;
}
base *= base;
e >>= 1;
}
return ans;
}
constexpr mint inv() const noexcept {
long long x, y;
auto d = ext_gcd((long long)_mod, (long long)v, x, y);
assert(d == 1);
return mint(y);
}
constexpr mint& operator/=(const mint& r) noexcept {
return (*this) *= r.inv();
}
constexpr mint operator/(const mint& r) const noexcept {
return mint(*this) *= r.inv();
}
constexpr friend mint operator/(const mint& l, i64 r) noexcept {
return mint(l) /= mint(r);
}
constexpr friend mint operator/(i64 l, const mint& r) noexcept {
return mint(l) /= mint(r);
}
};
}; // namespace kyopro
/**
* @brief static modint
*/
#line 2 "Library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 6 "Library/src/stream.hpp"
namespace kyopro {
inline void single_read(char& c) {
c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_read(T& a) {
a = 0;
bool is_negative = false;
char c = getchar_unlocked();
while (isspace(c)) {
c = getchar_unlocked();
}
if (c == '-') is_negative = true, c = getchar_unlocked();
while (isdigit(c)) {
a = 10 * a + (c - '0');
c = getchar_unlocked();
}
if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_read(T& a) {
long long x;
single_read(x);
a = T(x);
}
inline void single_read(std::string& str) noexcept {
char c = getchar_unlocked();
while (isspace(c)) c = getchar_unlocked();
while (!isspace(c)) {
str += c;
c = getchar_unlocked();
}
}
template<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
single_read(head), read(tail...);
}
inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
if (!a) {
putchar_unlocked('0');
return;
}
if constexpr (std::is_signed_v<T>) {
if (a < 0) putchar_unlocked('-'), a *= -1;
}
constexpr int d = std::numeric_limits<T>::digits10;
char s[d + 1];
int now = d + 1;
while (a) {
s[--now] = (char)'0' + a % 10;
a /= 10;
}
while (now <= d) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_write(T a) noexcept {
single_write(a.val());
}
inline void single_write(const std::string& str) noexcept {
for (auto c : str) {
putchar_unlocked(c);
}
}
template <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
single_write(head);
putchar_unlocked(' ');
write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
write(x...);
putchar_unlocked('\n');
}
}; // namespace kyopro
/**
* @brief
*/
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
const long double pi = acosl(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
return a > b && (a = b, true);
}
#line 5 "b.cpp"
using namespace std;
using namespace kyopro;
constexpr int MAX = 1e5;
using mint = modint<998244353>;
int main() {
int n;
read(n);
vector<int> a(n);
rep(i, n) read(a[i]);
vector dp(MAX + 1, mint::raw(1));
for (int i = 1; i < n; ++i) {
rep(i, (int)dp.size() - 1) dp[i + 1] += dp[i];
vector ndp(MAX + 1, mint());
rep(x, (int)ndp.size() - a[i]) {
int ma = min({MAX, MAX - a[i - 1], x, x + a[i] - a[i - 1]});
if (ma < 0) continue;
ndp[x] = dp[ma];
}
swap(dp, ndp);
}
put(accumulate(all(dp), mint()));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0