Submission #969449

#	Time	Username	Problem	Language	Result	Execution time	Memory
969449		kilkuwu	Boat (APIO16_boat)	C++17	100 / 100	1363 ms	8656 KiB

boat

#include <bits/stdc++.h>
 
#define nl '\n'
 
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
 
template <int md>
struct Modular {
  int v;
 
  constexpr Modular() : v(0) {}
 
  template <typename T>
  static inline int normalize(const T& x) {
    int res = -md <= x && x < md ? static_cast<int>(x) : static_cast<int>(x % md);
    return res + (res < 0) * md;
  }
  
  static constexpr int mod() {
    return md;
  }
 
  template <typename U>
  Modular(const U& x) : v(normalize(x)) {}
 
  const int& operator()() const { return v; }
 
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(v);
  }
 
  using M = Modular;
 
  constexpr static inline M _raw(int x) {
    static_assert(x >= 0 && x < md);
    M res;
    res.v = x;
    return res;
  }
 
  template <typename U>
  friend std::enable_if_t<std::is_integral_v<U>, M> power(M b, U e) {
    assert(e >= 0);
    M ans = 1;
    while (e) {
      if (e & 1) ans *= b;
      b *= b;
      e >>= 1;
    }
    return ans;
  }
 
  M inv() const {
    M res = power(*this, md - 2);
    return res;
  }
 
  M& operator+=(const M& y) { return v += y.v, v -= (v >= md) * md, *this; }
  M& operator-=(const M& y) { return v -= y.v, v += (v < 0) * md, *this; }
  M& operator*=(const M& y) { return v = (int64_t) v * y.v % md, *this; }
  M& operator/=(const M& y) { return *this *= y.inv(); }
 
  M& operator++() { return *this += _raw(1); }
  M& operator--() { return *this -= _raw(1); }
 
  M operator++(int) {
    M res(*this);
    return *this += _raw(1), res;
  }
 
  M operator--(int) {
    M res(*this);
    return *this -= _raw(1), res;
  }
 
  M operator-() const { return M(-v); }
 
  friend bool operator==(const M& x, const M& y) { return x.v == y.v; }
  friend bool operator<(const M& x, const M& y) { return x.v < y.v; }
  friend bool operator>(const M& x, const M& y) { return x.v > y.v; }
  friend bool operator<=(const M& x, const M& y) { return x.v <= y.v; }
  friend bool operator>=(const M& x, const M& y) { return x.v >= y.v; }
  friend bool operator!=(const M& x, const M& y) { return x.v != y.v; }
 
  template <typename Istream>
  friend Istream& operator>>(Istream& is, M& y) {
    int64_t x;
    is >> x;
    y.v = y.normalize(x);
    return is;
  }
 
  template <typename Ostream>
  friend Ostream& operator<<(Ostream& os, const M& y) {
    return os << y.v;
  }
 
  friend M operator+(const M& x, const M& y) { return M(x) += y; }
  friend M operator-(const M& x, const M& y) { return M(x) -= y; }
  friend M operator*(const M& x, const M& y) { return M(x) *= y; }
  friend M operator/(const M& x, const M& y) { return M(x) /= y; }
};
 
constexpr int md = 1e9 + 7;
using Mint = Modular<md>;

template <typename M>
struct Comb {
  std::vector<M> _fact, _finv;

  Comb() : _fact(1, 1), _finv(1, 1) {}

  inline int size() const { return static_cast<int>(_fact.size()); }

  void _double_extend() {
    int old_size = size();
    int new_size = std::min(M::mod(), size() * 2);

    _fact.resize(new_size);
    _finv.resize(new_size);

    for (int i = old_size; i < new_size; i++) {
      _fact[i] = _fact[i - 1] * i;
    }
    
    _finv[new_size - 1] = _fact[new_size - 1].inv();
    for (int i = new_size - 2; i >= old_size; i--) {
      _finv[i] = _finv[i + 1] * (i + 1);
    }
  }

  /**
   * Calculate ***n** choose **k***.
  */
  M operator()(int n, int k) {
    if (k > n || k < 0) return M();
    while (size() <= n) {
      _double_extend();
    }
    return _fact[n] * _finv[n - k] * _finv[k];
  }

  M lucas(int64_t n, int64_t k) {
    if (k > n) return 0;
    if (n < md) return this->operator()(n, k);
    return lucas(n / md, k / md) * this->operator()(n % md, k % md);
  }
};

Comb<Mint> C;
 
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n;
  std::cin >> n;
  std::vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) std::cin >> a[i] >> b[i], b[i]++;
 
  std::vector<int> vals(a.begin(), a.end());
  vals.insert(vals.end(), b.begin(), b.end());
  std::sort(vals.begin(), vals.end());
  vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
  dbg(vals);
 
  int num_segments = vals.size() - 1;
 
  for (int i = 0; i < n; i++) {
    a[i] = std::lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    b[i] = std::lower_bound(vals.begin(), vals.end(), b[i]) - vals.begin();
    dbg(a[i], b[i]);
  }
 
  std::vector<std::vector<Mint>> choose(num_segments, std::vector<Mint>(n + 1));
  std::vector<std::vector<Mint>> prepared(num_segments, std::vector<Mint>(n + 1));
 
  for (int i = 0; i < num_segments; i++) {
    int len = vals[i + 1] - vals[i];
    choose[i][0] = 1;
    for (int j = 0; j < n; j++) {
      choose[i][j + 1] = choose[i][j] * (len - j) / (j + 1);
    }
    for (int cnt = 1; cnt <= n; cnt++) {
      prepared[i][cnt] = 0;
      for (int j = 0; j < cnt; j++) {
        prepared[i][cnt] += C(cnt - 1, j) * choose[i][j + 1];
      }
    }
  }

  
 
 
  std::vector<std::vector<Mint>> dp(n + 1, std::vector<Mint>(num_segments + 1));
  std::vector<std::vector<Mint>> ff(n + 1, std::vector<Mint>(num_segments + 1));
 
 
  dp[n].back() = 1;
  for (int j = 0; j <= num_segments; j++) {
    ff[n][j] = 1;
  }
 
  Mint ans = 0;
 
  for (int i = n - 1; i >= 0; i--) {
    for (int j = num_segments - 1; j >= 0; j--) {
      if (a[i] <= j && j < b[i]) {
        int cnt = 0;
        for (int k = i; k < n; k++) {
          cnt += a[k] <= j && j < b[k];
          Mint mul = prepared[j][cnt];
          dbg(i, j, k, cnt, mul, ff[k + 1][j + 1], mul * ff[k + 1][j + 1]);
          dp[i][j] += ff[k + 1][j + 1] * mul;
        }
      }
      ans += dp[i][j];
      dbg(i, j, dp[i][j]);
      ff[i][j] = ff[i][j + 1] + dp[i][j];
    }
  }
 
  std::cout << ans << nl;
  // 4 
  // 4 7 
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42