QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617396 | #2834. Nonsense | YuJiahe | WA | 128ms | 99468kb | C++23 | 1.5kb | 2024-10-06 15:21:13 | 2024-10-06 15:21:14 |
Judging History
answer
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define mod 998244353
using namespace std;
const int N = 5005, M = N << 1;
int n, q, X, Y, iv, inv[M], g[M], Fx[M], Fy[M], f[N][N];
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
inline void mul(int& x, int y){x = 1ll * x * y % mod;}
inline int qpow(int bse, int p){int ans = 1;for (;p;p >>= 1, mul(bse, bse)) if (p & 1) mul(ans, bse);return ans;}
inline int F(int a, int b){if (a == -1) return Fy[b];if (b == -1) return Fx[a];return f[a][b];}
int main(){inv[1] = 1;
for (int i = 2;i <= M - 9;i ++)
inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
while (~scanf("%d%d%d%d", &n, &X, &Y, &q)){
if (X == Y){g[0] = (n + 1ll) * qpow(X, n) % mod, X = qpow(X, mod - 2);
for (int i = 1;i <= M - 10 && i <= n;i ++)
mul(g[i] = g[i - 1], n - i + 1), mul(g[i], inv[i + 1]), mul(g[i], X);
for (int a, b;q --;) scanf("%d%d", &a, &b), printf("%d\n", g[a + b]);continue;
}iv = qpow((X - Y + mod) % mod, mod - 2);
Fx[0] = qpow(X, n + 1), Fy[0] = qpow(Y, n + 1), X = qpow(X, mod - 2), Y = qpow(Y, mod - 2);
for (int i = 1;i <= N - 5 && i <= n;i ++)
mul(Fx[i] = Fx[i - 1], X), mul(Fx[i], n - i + 2), mul(Fx[i], inv[i]),
mul(Fy[i] = Fy[i - 1], Y), mul(Fy[i], n - i + 2), mul(Fy[i], inv[i]);
for (int a = 0;a <= n && a <= N - 5;a ++)
for (int b = 0;b <= n && b <= N - 5;b ++)
add(f[a][b] = F(a, b - 1), mod - F(a - 1, b)), mul(f[a][b], iv);
for (int a, b;q --;) scanf("%d%d", &a, &b), printf("%d\n", F(a, b));
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3992kb
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: 128ms
memory: 99468kb
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'