QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618220 | #2834. Nonsense | hcywoi | WA | 216ms | 101796kb | C++23 | 5.9kb | 2024-10-06 19:54:56 | 2024-10-06 19:54:57 |
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() {
// freopen("count.in", "r", stdin);
// freopen("count.out", "w", stdout);
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";
} 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: 3764kb
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: 0
Accepted
time: 8ms
memory: 22692kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 1 1
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 216ms
memory: 101796kb
input:
1000000000 998244351 998244352 1 5000 5000
output:
663228915
result:
ok single line: '663228915'
Test #4:
score: -100
Wrong Answer
time: 20ms
memory: 3640kb
input:
105886041 9 3 200 4 3 5 1 1 1 4 1 3 3 1 5 2 1 1 5 2 1 1 5 3 3 4 4 2 1 4 4 1 2 5 2 5 2 2 5 4 5 3 3 4 3 1 4 3 1 5 4 5 3 5 2 5 3 3 3 1 3 4 3 2 3 3 5 1 3 3 5 2 3 4 4 3 4 5 5 2 3 1 1 3 3 4 2 1 4 4 5 2 3 1 5 2 2 4 2 5 5 2 1 4 3 3 3 3 1 2 1 2 5 1 1 4 4 1 5 1 5 3 1 3 2 2 2 4 1 5 5 3 4 2 2 2 1 5 3 5 3 2 2 1 ...
output:
721440251 764408668 442427888 914530150 115811774 360614503 666106268 360614503 666106268 360614503 115811774 166867820 666106268 166867820 985976063 717651702 717651702 405340273 435048189 115811774 721440251 719754512 660548079 998056822 165742634 717651702 165742634 115811774 407319461 721440251 ...
result:
wrong answer 30605th lines differ - expected: '0', found: '1'