QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#755714 | #9631. Median Replacement | Bigmonster# | TL | 1ms | 3704kb | C++17 | 6.3kb | 2024-11-16 17:56:05 | 2024-11-16 17:56:06 |
Judging History
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 = 10000;
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(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: 3652kb
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: 1ms
memory: 3704kb
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: 1ms
memory: 3584kb
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...