QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618222 | #2834. Nonsense | hcywoi | WA | 8ms | 22756kb | C++23 | 5.9kb | 2024-10-06 19:56:09 | 2024-10-06 19:56:09 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
T qmi(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<int P>
struct modint {
int x;
constexpr modint() : x{} {}
constexpr modint(i64 x) : x{norm(x % getmod())} {}
static int mod;
constexpr static int getmod() {
if (P > 0) {
return P;
} else {
return mod;
}
}
constexpr static void setmod(int m) {
mod = m;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getmod();
}
if (x >= getmod()) {
x -= getmod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr modint operator-() const {
modint res;
res.x = norm(getmod() - x);
return res;
}
constexpr modint inv() const {
assert(x != 0);
return qmi(*this, getmod() - 2);
}
constexpr modint &operator*= (modint v) & {
x = 1LL * x * v.x % getmod();
return *this;
}
constexpr modint &operator+= (modint v) & {
x = norm(x + v.x);
return *this;
}
constexpr modint &operator-= (modint v) & {
x = norm(x - v.x);
return *this;
}
constexpr modint &operator/= (modint v) & {
return *this *= v.inv();
}
friend constexpr modint operator- (modint a, modint b) {
modint res = a;
res -= b;
return res;
}
friend constexpr modint operator+ (modint a, modint b) {
modint res = a;
res += b;
return res;
}
friend constexpr modint operator* (modint a, modint b) {
modint res = a;
res *= b;
return res;
}
friend constexpr modint operator/ (modint a, modint b) {
modint res = a;
res /= b;
return res;
}
friend constexpr std::istream &operator>> (std::istream& is, modint& a) {
i64 v;
is >> v;
a = modint(v);
return is;
}
friend constexpr std::ostream &operator<< (std::ostream& os, const modint& a) {
return os << a.val();
}
friend constexpr bool operator== (modint a, modint b) {
return a.val() == b.val();
}
friend constexpr bool operator!= (modint a, modint b) {
return a.val() != b.val();
}
};
constexpr int P = 998244353;
using mint = modint<P>;
struct Comb {
int n;
std::vector<mint> fact;
std::vector<mint> invefact;
std::vector<mint> inve;
Comb() : n{0}, fact{1}, invefact{1}, inve{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
if (m <= n) return;
fact.resize(m + 1);
invefact.resize(m + 1);
inve.resize(m + 1);
for (int i = n + 1; i <= m; i ++ ) {
fact[i] = fact[i - 1] * i;
}
invefact[m] = fact[m].inv();
for (int i = m; i > n; i -- ) {
invefact[i - 1] = invefact[i] * i;
inve[i] = invefact[i] * fact[i - 1];
}
n = m;
}
mint fac(int m) {
if (m > n) init(2 * m);
return fact[m];
}
mint invfac(int m) {
if (m > n) init(2 * m);
return invefact[m];
}
mint inv(int m) {
if (m > n) init(2 * m);
return inve[m];
}
mint binom(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
} comb;
mint f[5005][5005];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, x, y, q;
while (std::cin >> n >> x >> y >> q) {
n ++ ;
int N = 0;
std::vector<int> a(q), b(q);
for (int i = 0; i < q; i ++ ) {
std::cin >> a[i] >> b[i];
if (x != y) {
N = std::max({N, a[i], b[i]});
} else {
N = std::max(N, a[i] + b[i] + 1);
}
}
std::vector<mint> sx(N + 1), sy(N + 1);
for (int i = 0; i <= N; i ++ ) {
sx[i] = qmi(mint(x), n - i);
sy[i] = qmi(mint(y), n - i);
}
std::vector<mint> down(N + 1);
down[0] = 1;
for (int i = 1; i <= N; i ++ ) {
down[i] = down[i - 1] * (n - i + 1);
}
auto binom = [&](int m) -> mint {
return down[m] * comb.invfac(m);
};
if (x == y) {
for (int i = 0; i < q; i ++ ) {
if (x == 0) {
std::cout << (a[i] + b[i] == n) << "\n";
} else {
std::cout << binom(a[i] + b[i] + 1) * sx[a[i] + b[i] + 1] << "\n";
}
}
continue;
}
const mint inv = mint(y - x).inv();
for (int a = 0; a <= N; a ++ ) {
for (int b = 0; b <= N; b ++ ) {
if (a == 0 && b == 0) {
f[a][b] = (binom(b) * sy[b] - binom(a) * sx[a]) * inv;
} else if (a == 0) {
f[a][b] = (binom(b) * sy[b] - f[a][b - 1]) * inv;
} else if (b == 0) {
f[a][b] = (f[a - 1][b] - binom(a) * sx[a]) * inv;
} else {
f[a][b] = (f[a - 1][b] - f[a][b - 1]) * inv;
}
}
}
for (int i = 0; i < q; i ++ ) {
std::cout << f[a[i]][b[i]] << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
3 1 2 2 1 1 1 2 100 2 3 1 1 1
output:
6 1 866021789
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 22756kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 0 1
result:
wrong answer 2nd lines differ - expected: '1', found: '0'