結果
| 問題 | No.1608 Yet Another Ants Problem |
| ユーザー |
 KoD
|
| 提出日時 | 2021-07-16 22:50:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 87 ms / 2,000 ms |
| コード長 | 8,271 bytes |
| コンパイル時間 | 2,072 ms |
| コンパイル使用メモリ | 206,732 KB |
| 最終ジャッジ日時 | 2025-01-23 02:29:51 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;using i128 = __int128_t;using u128 = __uint128_t;using isize = std::ptrdiff_t;using usize = std::size_t;class rep {struct Iter {usize itr;constexpr Iter(const usize pos) noexcept : itr(pos) {}constexpr void operator++() noexcept { ++itr; }constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }constexpr usize operator*() const noexcept { return itr; }};const Iter first, last;public:explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}constexpr Iter begin() const noexcept { return first; }constexpr Iter end() const noexcept { return last; }};class revrep {struct Iter {usize itr;constexpr Iter(const usize pos) noexcept : itr(pos) {}constexpr void operator++() noexcept { --itr; }constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }constexpr usize operator*() const noexcept { return itr; }};const Iter first, last;public:explicit constexpr revrep(const usize first, const usize last) noexcept: first(last - 1), last(std::min(first, last) - 1) {}constexpr Iter begin() const noexcept { return first; }constexpr Iter end() const noexcept { return last; }};template <class T> constexpr T totient(T x) {T ret = x;for (T i = 2; i * i <= x; ++i) {if (x % i == 0) {ret /= i;ret *= i - 1;while (x % i == 0) x /= i;}}if (x > 1) {ret /= x;ret *= x - 1;}return ret;}template <class T> constexpr T rem_euclid(T value, const T& mod) { return (value %= mod) >= 0 ? value : value + mod; }template <u32 MOD, std::enable_if_t<((u32)1 <= MOD and MOD <= ((u32)1 << 31))>* = nullptr> class StaticModint {using Mint = StaticModint;static inline constexpr u32 PHI = totient(MOD);u32 v;public:static constexpr u32 mod() noexcept { return MOD; }template <class T, std::enable_if_t<std::is_signed_v<T> and std::is_integral_v<T>>* = nullptr>static constexpr T normalize(const T x) noexcept {return rem_euclid<std::common_type_t<T, i64>>(x, MOD);}template <class T, std::enable_if_t<std::is_unsigned_v<T> and std::is_integral_v<T>>* = nullptr>static constexpr T normalize(const T x) noexcept {return x % MOD;}constexpr StaticModint() noexcept : v(0) {}template <class T> constexpr StaticModint(const T x) noexcept : v(normalize(x)) {}template <class T> static constexpr Mint raw(const T x) noexcept {Mint ret;ret.v = x;return ret;}constexpr u32 get() const noexcept { return v; }constexpr Mint neg() const noexcept { return raw(v == 0 ? 0 : MOD - v); }constexpr Mint inv() const noexcept { return pow(PHI - 1); }constexpr Mint pow(u64 exp) const noexcept {Mint ret(1), mult(*this);for (; exp > 0; exp >>= 1) {if (exp & 1) ret *= mult;mult *= mult;}return ret;}constexpr Mint operator-() const noexcept { return neg(); }constexpr Mint operator~() const noexcept { return inv(); }constexpr Mint operator+(const Mint& rhs) const noexcept { return Mint(*this) += rhs; }constexpr Mint& operator+=(const Mint& rhs) noexcept {if ((v += rhs.v) >= MOD) v -= MOD;return *this;}constexpr Mint operator-(const Mint& rhs) const noexcept { return Mint(*this) -= rhs; }constexpr Mint& operator-=(const Mint& rhs) noexcept {if (v < rhs.v) v += MOD;v -= rhs.v;return *this;}constexpr Mint operator*(const Mint& rhs) const noexcept { return Mint(*this) *= rhs; }constexpr Mint& operator*=(const Mint& rhs) noexcept {v = (u64)v * rhs.v % MOD;return *this;}constexpr Mint operator/(const Mint& rhs) const noexcept { return Mint(*this) /= rhs; }constexpr Mint& operator/=(const Mint& rhs) noexcept { return *this *= rhs.inv(); }constexpr bool operator==(const Mint& rhs) const noexcept { return v == rhs.v; }constexpr bool operator!=(const Mint& rhs) const noexcept { return v != rhs.v; }friend std::ostream& operator<<(std::ostream& stream, const Mint& rhs) { return stream << rhs.v; }};using Modint1000000007 = StaticModint<1000000007>;using Modint998244353 = StaticModint<998244353>;constexpr u64 ceil_log2(const u64 x) {u64 e = 0;while (((u64)1 << e) < x) ++e;return e;}template <class F> class AutoReallocation {using R = typename decltype(std::declval<F>()((usize)0))::value_type;F func;mutable std::vector<R> data;public:explicit AutoReallocation(F&& f) : func(std::forward<F>(f)), data() {}void reserve(const usize size) const {if (data.size() < size) data = func(((usize)1 << ceil_log2(size)));}R operator[](const usize i) const {reserve(i + 1);return data[i];}};template <class F> decltype(auto) auto_realloc(F&& f) {using G = std::decay_t<F>;return AutoReallocation<G>(std::forward<G>(f));}template <class M> struct ModintUtil {static inline const auto fact = auto_realloc([](const usize n) {std::vector<M> ret(n);ret[0] = M(1);for (const usize i : rep(1, n)) {ret[i] = ret[i - 1] * M(i);}return ret;});static inline const auto inv = auto_realloc([](const usize n) {std::vector<M> ret(n);if (n == 1) return ret;ret[1] = M(1);for (const usize i : rep(2, n)) {ret[i] = -M(M::mod() / i) * ret[M::mod() % i];}return ret;});static inline const auto inv_fact = auto_realloc([](const usize n) {std::vector<M> ret(n);ret[0] = M(1);for (const usize i : rep(1, n)) {ret[i] = ret[i - 1] * inv[i];}return ret;});static M binom(const usize n, const usize k) {assert(k <= n);return fact[n] * inv_fact[n - k] * inv_fact[k];}static M factpow(const usize n, const usize k) {assert(k <= n);return fact[n] * inv_fact[n - k];}static M homo(const usize n, const usize k) {if (n == 0 and k == 0) return M(1);return binom(n + k - 1, k);}};template <class T> using Vec = std::vector<T>;using Fp = Modint998244353;using Util = ModintUtil<Fp>;void main_() {usize N;u32 L;std::cin >> N >> L;Vec<u32> A(N);for (auto& x : A) {std::cin >> x;}Vec<Fp> ans(N);// >>>>>, <<<<<ans[0] += 1;ans[N - 1] += 1;// <<<>>>for (const auto i : rep(0, N - 1)) {if (A[i] >= L - A[i + 1]) {ans[i] += 1;} else {ans[i + 1] += 1;}}Vec<Vec<Fp>> sum(N, Vec<Fp>(N));for (const auto i : rep(0, N)) {for (const auto j : rep(0, i + 1)) {sum[i][j] = Util::binom(i, j);}}for (const auto i : revrep(0, N - 1)) {for (const auto j : rep(0, N)) {sum[i][j] += sum[i + 1][j];}}for (const auto r : rep(0, N - 1)) {if (A[N - 1] < L - A[r]) {continue;}usize l = N - 1;while (r + 1 < l and A[l - 1] >= L - A[r]) {l -= 1;}for (const auto k : rep(0, N - r - 1)) {ans[r + k] += sum[l - r - 1][k] - sum[N - r - 1][k];}}for (const auto l : rep(1, N)) {if (L - A[0] <= A[l]) {continue;}usize r = 0;while (r + 1 < l and L - A[r + 1] > A[l]) {r += 1;}for (const auto k : rep(0, l)) {ans[l - k] += sum[l - r - 1][k] - sum[l][k];}}for (const auto x : ans) {std::cout << x << '\n';}}int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);main_();return 0;}