QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755738#9631. Median ReplacementBigmonster#TL 0ms3852kbC++176.3kb2024-11-16 17:58:242024-11-16 17:58:25

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 17:58:25]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3852kb
  • [2024-11-16 17:58:24]
  • 提交

answer

#include <algorithm>
#include <iterator>
#ifdef LOCAL
#include "dependencies.h"
#else
#include <bits/stdc++.h>
#endif

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)                                                             \
  do {                                                                         \
  } while (false)
#endif

template <typename T> bool chkmin(T &x, const T &y) {
  return x > y ? x = y, true : false;
}
template <typename T> bool chkmax(T &x, const T &y) {
  return x < y ? x = y, true : false;
}

#ifdef ATCODER
#include "atcoder/all"
#endif

template <unsigned int P> struct Fp {
  unsigned int v = 0;

  // reflection
  template <typename T = int> static constexpr T mod() { return P; }
  template <typename T = int> constexpr T val() { return v; }

  // constructor
  constexpr Fp() = default;
  template <typename T> constexpr Fp(T x) : v(x % mod()) {
    if constexpr (std::is_signed_v<T>) {
      if (v >> 31) {
        v += P;
      }
    }
  }

  // io
  friend std::istream &operator>>(std::istream &is, Fp &rhs) {
    long long v;
    is >> v;
    rhs = v;
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, Fp rhs) {
    return os << rhs.v;
  }

  // comparision
  friend constexpr bool operator==(Fp lhs, Fp rhs) { return lhs.v == rhs.v; }
  friend constexpr bool operator!=(Fp lhs, Fp rhs) { return lhs.v != rhs.v; }

  // arithmetic
  constexpr Fp &operator+=(Fp rhs) {
    v += rhs.v;
    if (v >= P)
      v -= P;
    return *this;
  }
  constexpr Fp &operator-=(Fp rhs) {
    v -= rhs.v;
    if (v >> 31)
      v += P;
    return *this;
  }
  constexpr Fp &operator*=(Fp rhs) {
    v = static_cast<unsigned long long>(v) * rhs.v % P;
    return *this;
  }
  constexpr Fp &operator/=(Fp rhs) {
    v = fpow(rhs.v, P - 2, v);
    return *this;
  }
  template <typename T> constexpr Fp &operator^=(T rhs) {
    v = fpow(v, rhs);
    return *this;
  }
  friend constexpr Fp operator+(Fp lhs, Fp rhs) { return lhs += rhs; }
  friend constexpr Fp operator-(Fp lhs, Fp rhs) { return lhs -= rhs; }
  friend constexpr Fp operator*(Fp lhs, Fp rhs) { return lhs *= rhs; }
  friend constexpr Fp operator/(Fp lhs, Fp rhs) { return lhs /= rhs; }
  template <typename T> friend constexpr Fp operator^(Fp lhs, T rhs) {
    return lhs ^= rhs;
  }
  constexpr Fp operator+() const { return *this; }
  constexpr Fp operator-() const { return Fp{} - *this; }
  constexpr Fp operator~() const { return fpow(v, P - 2); }
  template <typename T> constexpr Fp pow(T exp) const { return fpow(v, exp); }

  // x^y * z
  template <typename T>
  static constexpr unsigned int fpow(unsigned long long x, T y,
                                     unsigned long long z = 1) {
    unsigned int n = y % (mod() - 1);
    if constexpr (std::is_signed_v<T>) {
      if (n >> 31) {
        n += P - 1;
      }
    }
    for (; n; n /= 2) {
      if (n & 1)
        z = z * x % P;
      x = x * x % P;
    }
    return z;
  }
};

using Z353 = Fp<998244353>;
using Z007 = Fp<1000000007>;
using Z009 = Fp<1000000009>;

template <typename Z> struct Combination {
  static inline std::vector<Z> inv{0, 1}, fac{1, 1}, fiv{1, 1};
  static inline int N = 2;
  static void fix(int n) {
    if (N >= n)
      return;
    inv.resize(n);
    fac.resize(n);
    fiv.resize(n);
    for (int i = N; i < n; ++i) {
      inv[i] = inv[Z::mod() % i] * (Z::mod() - Z::mod() / i);
      fac[i] = fac[i - 1] * i;
      fiv[i] = fiv[i - 1] * inv[i];
    }
    N = n;
  }
  static Z inverse(int n) {
    fix(n + 1);
    return inv[n];
  }
  static Z factorial(int n) {
    fix(n + 1);
    return fac[n];
  }
  static Z facinv(int n) {
    fix(n + 1);
    return fiv[n];
  }
  static Z C(int n, int m) {
    fix(n + 1);
    return fac[n] * fiv[m] * fiv[n - m];
  }
};

void initialize() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(10);
}

template <typename T>
using Heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <typename T> void unique(std::vector<T> &a) {
  std::sort(a.begin(), a.end());
  a.erase(std::unique(a.begin(), a.end()), a.end());
}

template <typename T> bool contains(const std::vector<T> &a, const T &x) {
  auto iter = std::lower_bound(a.begin(), a.end(), x);
  return iter != a.end() && *iter == x;
}

void solution(int cas);

int main() {
  initialize();
  int T = 1;
  std::cin >> T;
  for (int cas = 1; cas <= T; ++cas) {
    solution(cas);
  }
}

void solution([[maybe_unused]] int cas) {
  // TODO
  using Z = Z007;
  using C = Combination<Z>;

  int n;
  std::cin >> n;
  std::vector<int> l(n), r(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> l[i];
  }
  for (int i = 0; i < n; ++i) {
    std::cin >> r[i];
    ++r[i];
  }

  auto DP = [&](int x) -> Z {
    std::array<Z, 4> dp = {};
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
      std::array<Z, 4> np = {};
      // 0 : 00
      // 1 : 01
      // 2 : 10
      // 3 : ok
      int a = std::max(0, r[i] - std::max(l[i], x)), b = r[i] - l[i] - a;
      np[0] = (dp[0] + dp[2]) * b;
      np[1] = dp[0] * a;
      np[2] = dp[1] * b;
      np[3] = (dp[1] + dp[2] + dp[3]) * a + dp[3] * b;
      dp.swap(np);
    }
    debug(x, dp[3]);
    return dp[3];
  };

  std::vector<int> key = l;
  std::copy(r.begin(), r.end(), std::back_inserter(key));
  unique(key);

  Z ans = (key[0] - 1) * DP(key[0]);
  constexpr int N = 200;
  for (int i = 1; i < (int)key.size(); ++i) {
    int L = key[i - 1], R = key[i];
    // for (int x = L; x < R; ++x) ans += DP(x);
    std::vector<Z> y(std::min(R - L, N) + 1);
    for (int x = L; x <= L + N && x < R; ++x) {
      y[x - L] = DP(x);
    }
    for (int i = 1; i <= N && L + i < R; ++i) {
      y[i] += y[i - 1];
    }

    ans += [](int n, std::vector<Z> y, int x) -> Z {
      if (x <= n)
        return y[x];
      Z g1 = 1, g2 = 0;
      for (int i = 1; i <= n; i++)
        g1 *= (x - i);
      for (int i = 1; i <= n; i++) {
        Z res = ((n - i) & 1 ? -y[i] : y[i]);
        res *= C::inverse(x - i);
        res *= C::facinv(i - 1);
        res *= C::facinv(n - i);
        g2 += res;
      }
      debug(g1, g2);
      return g1 * g2;
    }(N, y, R - L - 1);
  }

  std::cout << ans << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

10
5
5 1 4 3 2
14 2 5 3 2
5
4 5 1 2 3
13 7 1 2 3
5
5 2 5 3 1
10 2 12 3 2
5
5 5 3 1 5
57 5 3 1 5
5
2 2 3 3 5
4 5 4 4 5
5
4 5 3 5 3
13 7 3 5 3
5
5 1 4 2 3
14 3 4 2 3
5
1 2 5 4 5
2 8 5 7 5
5
1 1 3 5 1
8 2 3 8 1
5
4 4 4 2 3
5 10 5 2 3

output:

180
170
650
265
182
173
120
296
192
131

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

10
5
1 2 2 5 3
6 4 2 6 3
5
4 4 1 4 3
6 7 2 5 3
5
5 3 4 2 4
5 7 5 2 6
5
1 5 3 5 2
7 7 3 5 2
5
1 3 3 2 2
10 5 3 2 2
5
4 4 4 5 3
4 11 9 5 3
5
5 3 2 1 3
13 5 2 1 5
5
5 4 1 2 5
10 6 1 2 5
5
3 5 3 4 2
5 9 3 5 2
5
1 1 3 2 1
7 3 3 3 1

output:

120
230
144
110
110
289
324
89
140
122

result:

ok 10 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

10
5
3 1 3 4 4
9 1 3 10 4
5
1 1 3 1 1
9 1 3 3 1
5
5 1 2 3 1
74 1 2 3 1
5
2 5 5 3 4
5 6 8 3 4
5
2 1 3 4 5
2 4 6 4 5
5
2 4 2 1 3
2 11 3 2 3
5
1 5 4 4 2
1 14 6 6 2
5
4 1 3 5 1
9 2 4 5 1
5
4 1 2 4 4
6 1 6 4 4
5
3 2 5 3 5
8 8 5 3 5

output:

196
76
140
172
72
80
486
84
65
224

result:

ok 10 lines

Test #4:

score: -100
Time Limit Exceeded

input:

10
5
676437428 903889545 700650370 965758082 146716866
676437431 903889567 700650370 965758082 146716866
5
517457740 64600397 388618400 783268973 388618400
517457797 64600397 388618400 783268973 388618400
5
971452763 106948541 259878781 537741075 9504353
971452780 106948544 259878781 537741075 95043...

output:


result: