結果
| 問題 |
No.2512 Mountain Sequences
|
| コンテスト | |
| ユーザー |
 suisen
|
| 提出日時 | 2023-10-21 01:13:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,343 ms / 3,000 ms |
| コード長 | 9,850 bytes |
| コンパイル時間 | 1,467 ms |
| コンパイル使用メモリ | 114,808 KB |
| 最終ジャッジ日時 | 2025-02-17 12:01:41 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 |
ソースコード
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
namespace suisen {
struct Mo {
Mo() = default;
Mo(const int n, const std::vector<std::pair<int, int>> &queries) : n(n), q(queries.size()), b(bucket_size(n, q)), qs(queries), ord(q) {
std::iota(ord.begin(), ord.end(), 0);
std::sort(
ord.begin(), ord.end(),
[&, this](int i, int j) {
const auto &[li, ri] = qs[i];
const auto &[lj, rj] = qs[j];
const int bi = li / b, bj = lj / b;
if (bi != bj) return bi < bj;
if (ri != rj) return bi & 1 ? ri > rj : ri < rj;
return li < lj;
}
);
}
// getter methods used in updating functions: AddL, DelL, etc.
auto get_left() const { return l; }
auto get_right() const { return r; }
auto get_range() const { return std::make_pair(l, r); }
auto get_query_id() const { return query_id; }
/**
* [Parameters]
* Eval : () -> T : return the current answer
* AddL : int -> any (discarded) : add `l` to the current range [l + 1, r)
* DelL : int -> any (discarded) : delete `l` from the current range [l, r)
* AddR : int -> any (discarded) : add `r` to the current range [l, r)
* DelR : int -> any (discarded) : delete `r` from the current range [l, r + 1)
*
* [Note]
* starting from the range [0, 0).
*/
template <typename Eval, typename AddL, typename DelL, typename AddR, typename DelR>
auto solve(Eval eval, AddL add_l, DelL del_l, AddR add_r, DelR del_r) {
l = 0, r = 0;
std::vector<decltype(eval())> res(q);
for (int qi : ord) {
const auto &[nl, nr] = qs[query_id = qi];
while (r < nr) add_r(r), ++r;
while (l > nl) --l, add_l(l);
while (r > nr) --r, del_r(r);
while (l < nl) del_l(l), ++l;
res[qi] = eval();
}
return res;
}
/**
* [Parameters]
* Eval : () -> T : return the current answer
* Add : int -> any (discarded) : add `i` to the current range [i + 1, r) or [l, i)
* Del : int -> any (discarded) : delete `i` from the current range [i, r) or [l, i + 1)
*
* [Note]
* starting from the range [0, 0).
*/
template <typename Eval, typename Add, typename Del>
auto solve(Eval eval, Add add, Del del) {
return solve(eval, add, del, add, del);
}
private:
int n, q, b;
int query_id = -1;
std::vector<std::pair<int, int>> qs;
std::vector<int> ord;
int l = 0, r = 0;
static int bucket_size(int n, int q) {
return std::max(1, int(::sqrt(3) * n / ::sqrt(std::max(1, 2 * q))));
}
};
} // namespace suisen
namespace suisen {
template <int base_as_int, typename mint>
struct static_pow_mods {
static_pow_mods() = default;
static_pow_mods(int n) { ensure(n); }
const mint& operator[](int i) const {
ensure(i);
return pows[i];
}
static void ensure(int n) {
int sz = pows.size();
if (sz > n) return;
pows.resize(n + 1);
for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
}
private:
static inline std::vector<mint> pows { 1 };
static inline mint base = base_as_int;
static constexpr int mod = mint::mod();
};
template <typename mint>
struct pow_mods {
pow_mods() = default;
pow_mods(mint base, int n) : base(base) { ensure(n); }
const mint& operator[](int i) const {
ensure(i);
return pows[i];
}
void ensure(int n) const {
int sz = pows.size();
if (sz > n) return;
pows.resize(n + 1);
for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
}
private:
mutable std::vector<mint> pows { 1 };
mint base;
static constexpr int mod = mint::mod();
};
}
#include <cassert>
namespace suisen {
template <typename T, typename U = T>
struct factorial {
factorial() = default;
factorial(int n) { ensure(n); }
static void ensure(const int n) {
int sz = _fac.size();
if (n + 1 <= sz) return;
int new_size = std::max(n + 1, sz * 2);
_fac.resize(new_size), _fac_inv.resize(new_size);
for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i;
_fac_inv[new_size - 1] = U(1) / _fac[new_size - 1];
for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i;
}
T fac(const int i) {
ensure(i);
return _fac[i];
}
T operator()(int i) {
return fac(i);
}
U fac_inv(const int i) {
ensure(i);
return _fac_inv[i];
}
U binom(const int n, const int r) {
if (n < 0 or r < 0 or n < r) return 0;
ensure(n);
return _fac[n] * _fac_inv[r] * _fac_inv[n - r];
}
U perm(const int n, const int r) {
if (n < 0 or r < 0 or n < r) return 0;
ensure(n);
return _fac[n] * _fac_inv[n - r];
}
private:
static std::vector<T> _fac;
static std::vector<U> _fac_inv;
};
template <typename T, typename U>
std::vector<T> factorial<T, U>::_fac{ 1 };
template <typename T, typename U>
std::vector<U> factorial<T, U>::_fac_inv{ 1 };
} // namespace suisen
namespace suisen {
// {n,m} in qs: Sum[i=0,n] r^i Binom[m,i]
template <typename Mint>
std::vector<Mint> binom_sum_prefix(const std::vector<std::pair<int, int>>& qs, const Mint& r = 1) {
const int q = qs.size();
std::vector<Mint> res(qs.size());
if (r == -1) {
factorial<Mint> fac;
for (int i = 0; i < q; ++i) {
auto [n, m] = qs[i];
n = std::min(n, m);
if (n < 0) {
res[i] = 0;
} else if (m == 0) {
// n = m = 0
res[i] = 1;
} else {
res[i] = (n % 2 == 1 ? -1 : +1) * fac.binom(m - 1, n);
}
}
return res;
}
std::vector<int> qid;
std::vector<std::pair<int, int>> ranges;
qid.reserve(q), ranges.reserve(q);
int max_m = 1;
for (int i = 0; i < q; ++i) {
auto [n, m] = qs[i];
n = std::min(n, m);
if (n < 0) {
res[i] = 0;
} else if (m == 0) {
// n = m = 0
res[i] = 1;
} else {
qid.push_back(i);
ranges.emplace_back(n, m);
max_m = std::max(max_m, m);
}
}
pow_mods<Mint> pow_r(r, max_m + 1);
factorial<Mint> fac(max_m + 1);
const Mint inv_r1 = (r + 1).inv();
Mo mo(max_m, std::move(ranges));
Mint sum = 1;
const std::vector<Mint> res_mo = mo.solve(
[&] {
return sum;
},
[&](const int n) { // Add Left
const int m = mo.get_right();
// (n + 1, m) -> (n, m)
sum -= pow_r[n + 1] * fac.binom(m, n + 1);
},
[&](const int n) { // Del Left
const int m = mo.get_right();
// (n, m) -> (n + 1, m)
sum += pow_r[n + 1] * fac.binom(m, n + 1);
},
[&](const int m) { // Add Right
const int n = mo.get_left();
// (n, m) -> (n, m + 1)
sum = (r + 1) * sum - pow_r[n + 1] * fac.binom(m, n);
},
[&](const int m) { // Del Right
const int n = mo.get_left();
// (n, m + 1) -> (n, m)
sum = (pow_r[n + 1] * fac.binom(m, n) + sum) * inv_r1;
}
);
for (int i = 0; i < int(qid.size()); ++i) res[qid[i]] = res_mo[i];
return res;
}
// {a,b,m} in qs: Sum[i=a,b] r^i Binom[m,i]
template <typename Mint>
std::vector<Mint> binom_sum(const std::vector<std::tuple<int, int, int>>& qs, const Mint& r = 1) {
const int q = qs.size();
std::vector<std::pair<int, int>> ls(q), rs(q);
for (int i = 0; i < q; ++i) {
const auto [a, b, m] = qs[i];
ls[i] = { a - 1, m };
rs[i] = { b, m };
}
std::vector<Mint> suml = binom_sum_prefix(ls, r);
std::vector<Mint> sumr = binom_sum_prefix(rs, r);
std::vector<Mint> sum(q);
for (int i = 0; i < q; ++i) sum[i] = sumr[i] - suml[i];
return sum;
}
} // namespace suisen
#include <iostream>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
constexpr int M = 400010;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int q;
std::cin >> q;
std::vector<std::pair<int, int>> qs(q);
for (int i = 0; i < q; ++i) {
int n, m;
std::cin >> n >> m;
qs[i] = { n, 2 * m };
}
const mint inv2 = mint(2).inv();
suisen::pow_mods<mint> pw(-inv2, 200010);
std::vector<mint> res = suisen::binom_sum_prefix<mint>(qs, -2);
for (int i = 0; i < q; ++i) {
auto [n, m] = qs[i];
std::cout << ((res[i] - 1) * -pw[n + 1]).val() << '\n';
}
return 0;
}