This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/arc108/tasks/arc108_e" #include <iostream> #include <atcoder/modint> #include "library/math/inv_mods.hpp" #include "library/datastructure/segment_tree/segment_tree.hpp" #include "library/datastructure/fenwick_tree/fenwick_tree_2d.hpp" using namespace suisen; using mint = atcoder::modint1000000007; mint op(mint x, mint y) { return x + y; } mint e() { return 0; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> a(n); inv_mods<mint> invs(n); for (int &e : a) std::cin >> e; a.insert(a.begin(), 0); a.insert(a.end(), n + 1); std::vector dp_segs(n + 2, SegmentTree<mint, op, e>(n + 2)); std::vector pd_segs(n + 2, SegmentTree<mint, op, e>(n + 2)); FenwickTree2D<int> ft_point(n + 2, n + 2); for (int i = 1; i <= n; ++i) ++ft_point[{i, a[i]}]; mint ans = 0; for (int w = 1; w <= n; ++w) { for (int l = 1, r = w; r <= n; ++l, ++r) { int vl = a[l - 1], vr = a[r + 1]; if (vl > vr) continue; int k = ft_point(l, r + 1, vl, vr); if (k == 0) continue; mint val = 1 + ((dp_segs[l](vl, vr) + pd_segs[r](vl, vr)) * invs[k]).val(); dp_segs[l][a[r + 1]] += val; pd_segs[r][a[l - 1]] += val; if (w == n) ans = val; } } std::cout << ans.val() << std::endl; return 0; }
#line 1 "test/src/datastructure/fenwick_tree/fenwick_tree_2d/random_is.test.cpp" #define PROBLEM "https://atcoder.jp/contests/arc108/tasks/arc108_e" #include <iostream> #include <atcoder/modint> #line 1 "library/math/inv_mods.hpp" #include <vector> namespace suisen { template <typename mint> class inv_mods { public: inv_mods() = default; inv_mods(int n) { ensure(n); } const mint& operator[](int i) const { ensure(i); return invs[i]; } static void ensure(int n) { int sz = invs.size(); if (sz < 2) invs = { 0, 1 }, sz = 2; if (sz < n + 1) { invs.resize(n + 1); for (int i = sz; i <= n; ++i) invs[i] = mint(mod - mod / i) * invs[mod % i]; } } private: static std::vector<mint> invs; static constexpr int mod = mint::mod(); }; template <typename mint> std::vector<mint> inv_mods<mint>::invs{}; template <typename mint> std::vector<mint> get_invs(const std::vector<mint>& vs) { const int n = vs.size(); mint p = 1; for (auto& e : vs) { p *= e; assert(e != 0); } mint ip = p.inv(); std::vector<mint> rp(n + 1); rp[n] = 1; for (int i = n - 1; i >= 0; --i) { rp[i] = rp[i + 1] * vs[i]; } std::vector<mint> res(n); for (int i = 0; i < n; ++i) { res[i] = ip * rp[i + 1]; ip *= vs[i]; } return res; } } #line 1 "library/datastructure/segment_tree/segment_tree.hpp" #include <cassert> #line 6 "library/datastructure/segment_tree/segment_tree.hpp" #line 1 "library/util/update_proxy_object.hpp" #line 1 "library/type_traits/type_traits.hpp" #include <limits> #line 6 "library/type_traits/type_traits.hpp" #include <type_traits> namespace suisen { template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>; template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; }; template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; }; template <typename T> static constexpr int bitnum_v = bitnum<T>::value; template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; }; template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value; template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; }; template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; }; template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type; template <typename T, typename = void> struct rec_value_type { using type = T; }; template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> { using type = typename rec_value_type<typename T::value_type>::type; }; template <typename T> using rec_value_type_t = typename rec_value_type<T>::type; template <typename T> class is_iterable { template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value; template <typename T> class is_writable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_writable_v = is_writable<T>::value; template <typename T> class is_readable { template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{}); static std::false_type test(...); public: static constexpr bool value = decltype(test(std::declval<T>()))::value; }; template <typename T> static constexpr bool is_readable_v = is_readable<T>::value; } // namespace suisen #line 5 "library/util/update_proxy_object.hpp" namespace suisen { template <typename T, typename UpdateFunc, constraints_t<std::is_invocable<UpdateFunc>> = nullptr> struct UpdateProxyObject { public: UpdateProxyObject(T &v, UpdateFunc update) : v(v), update(update) {} operator T() const { return v; } auto& operator++() && { ++v, update(); return *this; } auto& operator--() && { --v, update(); return *this; } auto& operator+=(const T &val) && { v += val, update(); return *this; } auto& operator-=(const T &val) && { v -= val, update(); return *this; } auto& operator*=(const T &val) && { v *= val, update(); return *this; } auto& operator/=(const T &val) && { v /= val, update(); return *this; } auto& operator%=(const T &val) && { v %= val, update(); return *this; } auto& operator =(const T &val) && { v = val, update(); return *this; } auto& operator<<=(const T &val) && { v <<= val, update(); return *this; } auto& operator>>=(const T &val) && { v >>= val, update(); return *this; } template <typename F, constraints_t<std::is_invocable_r<T, F, T>> = nullptr> auto& apply(F f) && { v = f(v), update(); return *this; } private: T &v; UpdateFunc update; }; } // namespace suisen #line 8 "library/datastructure/segment_tree/segment_tree.hpp" namespace suisen { template <typename T, T(*op)(T, T), T(*e)()> class SegmentTree { public: SegmentTree() : SegmentTree(0) {} explicit SegmentTree(int n) : SegmentTree(std::vector<T>(n, e())) {} SegmentTree(const std::vector<T> &a) : n(a.size()), m(ceil_pow2(n)), data(2 * m, e()) { build(a); } void build(const std::vector<T> &a) { assert(int(a.size()) <= m); std::copy(a.begin(), a.end(), data.begin() + m); for (int k = m - 1; k > 0; --k) update(k); } const T& get(int i) const { assert(0 <= i and i < n); return data[i + m]; } T operator()(int l, int r) const { T res_l = e(), res_r = e(); for (l += m, r += m; l < r; l >>= 1, r >>= 1) { if (l & 1) res_l = op(res_l, data[l++]); if (r & 1) res_r = op(data[--r], res_r); } return op(res_l, res_r); } T prod(int l, int r) const { return (*this)(l, r); } T prefix_prod(int r) const { return (*this)(0, r); } T suffix_prod(int l) const { return (*this)(l, m); } T all_prod() const { return data[1]; } void set(int i, const T &val) { (*this)[i] = val; } auto operator[](int i) { assert(0 <= i and i < n); int k = i + m; return UpdateProxyObject { data[k], [this, k]{ update_from(k); } }; } template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr> int max_right(int l, const Pred &f) const { assert(0 <= l and l <= n); assert(f(e)); if (l == n) return n; l += m; T sum_l = e; do { while (l % 2 == 0) l >>= 1; if (not f(op(sum_l, data[l]))) { while (l < m) { l = 2 * l; if (f(op(sum_l, data[l]))) sum_l = op(sum_l, data[l++]); } return l - m; } sum_l = op(sum_l, data[l]); l++; } while ((l & -l) != l); return n; } template <bool(*f)(T)> int max_right(int l) { return max_right(l, f); } template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr> int min_left(int r, const Pred &f) const { assert(0 <= r && r <= n); assert(f(e)); if (r == 0) return 0; r += m; T sum_r = e; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (not f(op(data[r], sum_r))) { while (r < m) { r = 2 * r + 1; if (f(op(data[r], sum_r))) sum_r = op(data[r--], sum_r); } return r + 1 - m; } sum_r = op(data[r], sum_r); } while ((r & -r) != r); return 0; } template <bool(*f)(T)> int min_left(int l) { return min_left(l, f); } private: int n, m; std::vector<T> data; static constexpr int ceil_pow2(int n) { int m = 1; while (m < n) m <<= 1; return m; } void update_from(int k) { for (k >>= 1; k; k >>= 1) update(k); } void update(int k) { data[k] = op(data[k * 2], data[k * 2 + 1]); } }; } // namespace suisen #line 1 "library/datastructure/fenwick_tree/fenwick_tree_2d.hpp" #line 5 "library/datastructure/fenwick_tree/fenwick_tree_2d.hpp" namespace suisen { template <typename T> class FenwickTree2D { public: FenwickTree2D() = default; explicit FenwickTree2D(int n, int m) : n(n), m(m), data(n, std::vector<T>(m, T{})) {} void add(int i, int j, T v) { for (int x = i + 1; x <= n; x += (x & -x)) for (int y = j + 1; y <= m; y += (y & -y)) { data[x - 1][y - 1] += v; } } T sum(int xl, int xr, int yl, int yr) const { return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl); } auto operator[](std::pair<int, int> index) { auto [i, j] = index; struct { int i, j; FenwickTree2D& ft; operator T() const { return ft.sum(i, i + 1, j, j + 1); } auto& operator++() { return *this += 1; } auto& operator--() { return *this -= 1; } auto& operator+=(T val) { ft.add(i, j, val); return *this; } auto& operator-=(T val) { ft.add(i, j, -val); return *this; } auto& operator*=(T val) { T cur = *this; ft.add(i, j, cur * val - cur); return *this; } auto& operator/=(T val) { T cur = *this; ft.add(i, j, cur / val - cur); return *this; } auto& operator%=(T val) { T cur = *this; ft.add(i, j, cur % val - cur); return *this; } auto& operator =(T val) { T cur = *this; ft.add(i, j, val - cur); return *this; } } obj{ i, j, *this }; return obj; } T operator()(int xl, int xr, int yl, int yr) const { return sum(xl, xr, yl, yr); } private: int n, m; std::vector<std::vector<T>> data; T sum(int xr, int yr) const { T s{}; for (int x = xr; x; x -= x & -x) for (int y = yr; y; y -= y & -y) { s += data[x - 1][y - 1]; } return s; } }; } // namespace suisen #line 9 "test/src/datastructure/fenwick_tree/fenwick_tree_2d/random_is.test.cpp" using namespace suisen; using mint = atcoder::modint1000000007; mint op(mint x, mint y) { return x + y; } mint e() { return 0; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<int> a(n); inv_mods<mint> invs(n); for (int &e : a) std::cin >> e; a.insert(a.begin(), 0); a.insert(a.end(), n + 1); std::vector dp_segs(n + 2, SegmentTree<mint, op, e>(n + 2)); std::vector pd_segs(n + 2, SegmentTree<mint, op, e>(n + 2)); FenwickTree2D<int> ft_point(n + 2, n + 2); for (int i = 1; i <= n; ++i) ++ft_point[{i, a[i]}]; mint ans = 0; for (int w = 1; w <= n; ++w) { for (int l = 1, r = w; r <= n; ++l, ++r) { int vl = a[l - 1], vr = a[r + 1]; if (vl > vr) continue; int k = ft_point(l, r + 1, vl, vr); if (k == 0) continue; mint val = 1 + ((dp_segs[l](vl, vr) + pd_segs[r](vl, vr)) * invs[k]).val(); dp_segs[l][a[r + 1]] += val; pd_segs[r][a[l - 1]] += val; if (w == n) ans = val; } } std::cout << ans.val() << std::endl; return 0; }