QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22030 | #2834. Nonsense | Qingyu | RE | 162ms | 103520kb | C++20 | 2.8kb | 2022-03-09 00:58:00 | 2022-04-30 00:41:54 |
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));
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';
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 5512kb
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: 12ms
memory: 9576kb
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: 162ms
memory: 103520kb
input:
1000000000 998244351 998244352 1 5000 5000
output:
663228915
result:
ok single line: '663228915'
Test #4:
score: -100
Dangerous Syscalls
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 ...