QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755610#9631. Median ReplacementBigmonster#WA 1ms3696kbC++176.2kb2024-11-16 17:45:052024-11-16 17:45:06

Judging History

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

  • [2024-11-16 17:45:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3696kb
  • [2024-11-16 17:45:05]
  • 提交

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, 3> dp = {};
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
      std::array<Z, 3> np = {};
      int a = std::max(0, r[i] - std::max(l[i], x)), b = r[i] - l[i] - a;
      np[0] = (dp[0] + dp[1]) * b;
      np[1] = dp[0] * a;
      np[2] = dp[1] * a + dp[2] * (a + b);
      dp.swap(np);
    }
    debug(x, dp[2]);
    return dp[2];
  };

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

  Z ans = 0;
  constexpr int N = 10000;
  for (int i = 1; i < (int)key.size(); ++i) {
    int L = key[i - 1], R = key[i];
      std::vector<Z> y(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: 0
Wrong Answer
time: 1ms
memory: 3696kb

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:

120
170
288
265
128
110
70
274
192
102

result:

wrong answer 1st lines differ - expected: '180', found: '120'