QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22031 | #2834. Nonsense | Qingyu | RE | 176ms | 103696kb | C++20 | 2.8kb | 2022-03-09 01:01:58 | 2022-04-30 00:41:58 |
Judging History
answer
#include <bits/stdc++.h>
const int mod = 998244353;
inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void upd(int &x, int y) { x = inc(x, y); }
inline void dpu(int &x, int y) { x = dec(x, y); }
inline void pud(int &x, int y) { x = mul(x, y); }
inline int fastpow(int x, int p) {
int r = 1;
while (p) {
if (p & 1) r = mul(r, x);
x = mul(x, x);
p >>= 1;
}
return r;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, x, y, q;
const int lim = 2e5 + 50;
std::vector<int> inv(lim), fact(lim), factinv(lim);
fact[0] = 1;
for (int i = 1; i < lim; ++i)
fact[i] = mul(i, fact[i - 1]);
factinv[lim - 1] = fastpow(fact[lim - 1], mod - 2);
for (int i = lim - 2; i >= 0; --i) {
factinv[i] = mul(i + 1, factinv[i + 1]);
}
for (int i = 1; i < lim; ++i) {
assert(mul(fact[i], factinv[i]) == 1);
}
for (int i = 1; i < lim; ++i)
inv[i] = mul(factinv[i], fact[i - 1]);
auto comb = [&](int n, int m) {
if (n < m) return 0;
return mul(mul(fact[n], factinv[m]), factinv[n - m]);
};
while (std::cin >> n >> x >> y >> q) {
if (std::cin.eof()) break;
std::vector<int> a(q), b(q);
int mx = 0, prod = 1;
for (int i = 0; i < q; ++i) {
std::cin >> a[i] >> b[i];
}
mx = std::max(*std::max_element(a.begin(), a.end()), *std::max_element(b.begin(), b.end())) + 1;
std::vector<std::vector<int>> f(mx + 1, std::vector<int>(mx + 1));
std::vector<int> binom(2 * mx + 1);
// C(n + 1, i)
binom[0] = 1;
for (int i = 1; i <= 2 * mx; ++i) {
binom[i] = mul(binom[i - 1], mul(inv[i], n + 2 - i));
}
if (x == y) {
std::vector<int> power(lim);
power[0] = 1;
for (int i = 0; i < q; ++i) {
int z = binom[a[i] + b[i] + 1];
std::cout << mul(z, fastpow(x, n - a[i] - b[i])) << '\n';
}
}
else {
f[0][0] = fastpow(inc(x, y), n);
int d = (x > y) ? inv[x - y] : mod - inv[y - x];
std::vector<int> pa(mx), pb(mx);
for (int i = 0; i < mx; ++i) {
pa[i] = fastpow(x, n + 1 - i);
pb[i] = fastpow(y, n + 1 - i);
}
f[0][0] = mul(d, dec(pa[0], pb[0]));
for (int i = 1; i < mx; ++i) {
int A = 0;
int B = mul(binom[i], pb[i]);
f[0][i] = dec(A, B);
A = mul(binom[i], pa[i]);
B = 0;
f[i][0] = dec(A, B);
}
for (int i = 1; i < mx; ++i) {
upd(f[0][i], f[0][i - 1]);
pud(f[0][i], d);
dpu(f[i][0], f[i - 1][0]);
pud(f[i][0], d);
}
for (int i = 1; i <= mx; ++i)
for (int j = 1; j <= mx; ++j) {
dpu(f[i][j], f[i - 1][j]);
upd(f[i][j], f[i][j - 1]);
pud(f[i][j], d);
}
for (int i = 0; i < q; ++i) {
std::cout << f[a[i]][b[i]] << '\n';
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 5448kb
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: 9484kb
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: 176ms
memory: 103696kb
input:
1000000000 998244351 998244352 1 5000 5000
output:
663228915
result:
ok single line: '663228915'
Test #4:
score: 0
Accepted
time: 50ms
memory: 6460kb
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:
ok 200000 lines
Test #5:
score: 0
Accepted
time: 30ms
memory: 6392kb
input:
405229773 25 79 200 3 3 5 5 5 5 1 5 2 4 2 4 3 1 3 3 5 4 1 5 2 1 3 1 4 1 2 5 1 4 4 4 4 1 5 5 5 3 2 2 1 1 2 1 4 2 4 4 2 3 5 1 4 3 2 3 3 4 4 3 2 2 3 3 1 4 5 3 2 2 3 1 1 1 3 3 3 5 1 3 5 2 1 1 1 4 5 5 5 5 4 1 2 5 2 5 1 4 1 1 3 3 5 4 1 2 1 1 2 5 4 3 5 4 3 3 5 2 3 3 4 1 2 3 2 5 1 3 4 3 4 4 4 2 5 1 2 5 3 5 ...
output:
52820293 692687559 692687559 899722361 150221007 150221007 570819646 52820293 9962865 899722361 594892845 570819646 90708097 161767707 25275214 680941576 90708097 692687559 142946866 827907378 868929596 594892845 73037078 680941576 897540013 658419918 202971687 897540013 38775730 202971687 827907378...
result:
ok 200000 lines
Test #6:
score: -100
Runtime Error
input:
205514256 631068448 638301474 200 2 5 2 4 1 4 1 5 4 2 1 5 4 2 1 2 5 4 3 2 3 5 4 3 2 4 4 5 3 2 5 5 1 1 3 2 3 2 5 2 4 2 4 3 4 2 3 5 2 4 5 1 2 1 2 3 3 1 5 1 3 1 1 3 2 5 5 4 4 5 2 1 5 4 5 1 2 3 5 3 5 2 1 2 2 2 5 2 2 4 1 1 3 1 1 3 4 4 2 3 1 2 2 4 1 1 1 5 3 5 2 2 2 2 1 5 2 5 5 2 2 5 3 1 1 3 5 1 5 3 2 3 3 ...