QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618176 | #2834. Nonsense | hcywoi | TL | 2ms | 5692kb | C++23 | 5.5kb | 2024-10-06 19:35:26 | 2024-10-06 19:35:32 |
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) {
if (x == y) {
while (q -- ) {
int a, b;
std::cin >> a >> b;
if (x == 0) {
std::cout << (a == b) << "\n";
} else {
std::cout << comb.binom(n + 1, a + b + 1) * qmi(mint(x), n - a - b) << "\n";
}
}
continue;
}
n ++ ;
const int N = std::min(5000, n);
const mint inv = mint(y - x).inv();
std::vector<mint> sx(N), sy(N);
for (int i = 0; i <= N; i ++ ) {
sx[i] = qmi(mint(x), n - i);
sy[i] = qmi(mint(y), n - i);
}
for (int a = 0; a <= N; a ++ ) {
for (int b = 0; b <= N; b ++ ) {
if (a == 0 && b == 0) {
f[a][b] = (comb.binom(n, b) * sy[b] - comb.binom(n, a) * sx[a]) * inv;
} else if (a == 0) {
f[a][b] = (comb.binom(n, b) * sy[b] - f[a][b - 1]) * inv;
} else if (b == 0) {
f[a][b] = (f[a - 1][b] - comb.binom(n, a) * sx[a]) * inv;
} else {
f[a][b] = (f[a - 1][b] - f[a][b - 1]) / (y - x);
}
}
}
while (q -- ) {
int a, b;
std::cin >> a >> b;
std::cout << f[a][b] << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5692kb
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
Time Limit Exceeded
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1