QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103214 | #2834. Nonsense | Leasier | TL | 7ms | 28804kb | C++14 | 4.1kb | 2023-05-04 19:44:40 | 2023-05-04 19:44:42 |
Judging History
answer
#include <stdio.h>
typedef long long ll;
const int N = 2e5 + 7, M = 5e3 + 1, K = 1e4 + 7, mod = 998244353;
int a[N], b[N];
ll inv[M + 7], c[M + 7][M + 7], val[K], power[K], ans[M + 7][M + 7];
inline void init(){
inv[0] = inv[1] = 1;
for (register int i = 2; i <= M; i++){
inv[i] = mod - (mod / i) * inv[mod % i] % mod;
}
}
inline int max(int a, int b){
return a > b ? a : b;
}
inline ll quick_pow(ll x, ll p, ll mod){
ll ans = 1;
while (p){
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
return ans;
}
int main(){
int n, x, y, q;
init();
while (scanf("%d %d %d %d", &n, &x, &y, &q) != EOF){
int maxa = 0, maxb = 0, maxab, sum;
for (register int i = 1; i <= q; i++){
scanf("%d %d", &a[i], &b[i]);
maxa = max(maxa, a[i]);
maxb = max(maxb, b[i]);
}
maxab = max(maxa, maxb);
sum = maxa + maxb;
for (register int i = 0; i <= maxab; i++){
c[i][0] = 1;
for (register int j = 1; j <= maxab; j++){
c[i][j] = c[i][j - 1] * (n - i - j + 1) % mod * inv[j] % mod;
}
}
if (x == 0){
power[sum] = quick_pow(y, n - sum, mod);
for (register int i = sum - 1; i >= 0; i--){
power[i] = power[i + 1] * y % mod;
}
for (register int i = 0; i <= maxa; i++){
for (register int j = 0; j <= maxb; j++){
ans[i][j] = c[i][j] * power[i + j] % mod;
}
}
} else if (y == 0){
power[sum] = quick_pow(x, n - sum, mod);
for (register int i = sum - 1; i >= 0; i--){
power[i] = power[i + 1] * x % mod;
}
for (register int i = 0; i <= maxa; i++){
for (register int j = 0; j <= maxb; j++){
ans[i][j] = c[j][i] * power[i + j] % mod;
}
}
} else {
val[0] = 1;
for (register int i = 1; i <= sum; i++){
val[i] = val[i - 1] * (n - i + 1) % mod * inv[i] % mod;
}
if (x == y){
power[sum] = quick_pow(x, n - sum, mod);
for (register int i = sum - 1; i >= 0; i--){
power[i] = power[i + 1] * x % mod;
}
for (register int i = 0; i <= maxa; i++){
for (register int j = 0; j <= maxb; j++){
ans[i][j] = val[i + j] * power[i + j] % mod;
}
}
} else {
ll q = x * quick_pow(y, mod - 2, mod) % mod, invqd = quick_pow(q - 1, mod - 2, mod), r = quick_pow(q, mod - 2, mod), invrd = quick_pow(r - 1, mod - 2, mod), inv_val = quick_pow(((x - y) % mod + mod) % mod, mod - 2, mod);
if (q == 1){
ll temp = 1;
for (register int i = 0; i <= maxa; i++){
if (i > 0) temp = temp * (n - i + 1) % mod * inv[i + 1] % mod;
ans[i][0] = temp * quick_pow(x, n - i, mod) % mod;
}
} else {
power[maxa] = quick_pow(q, n - maxa, mod);
for (register int i = maxa - 1; i >= 0; i--){
power[i] = power[i + 1] * q % mod;
}
for (register int i = 0; i <= maxa; i++){
ll val = (quick_pow(q, n - i + 1, mod) - 1) * invqd % mod;
for (register int j = 1; j <= i; j++){
val = ((power[i - j] * c[i - j][j] % mod - val) * q % mod * invqd % mod + mod) % mod;
}
ans[i][0] = val * quick_pow(y, n, mod) % mod * quick_pow(x, mod - i - 1, mod) % mod;
}
}
if (r == 1){
ll temp = 1;
for (register int i = 0; i <= maxb; i++){
if (i > 0) temp = temp * (n - i + 1) % mod * inv[i + 1] % mod;
ans[i][0] = temp * quick_pow(y, n - i, mod) % mod;
}
} else {
power[maxb] = quick_pow(r, n - maxb, mod);
for (register int i = maxb - 1; i >= 0; i--){
power[i] = power[i + 1] * r % mod;
}
for (register int i = 1; i <= maxb; i++){
ll val = (quick_pow(r, n - i + 1, mod) - 1) * invrd % mod;
for (register int j = 1; j <= i; j++){
val = ((power[i - j] * c[i - j][j] % mod - val) * r % mod * invrd % mod + mod) % mod;
}
ans[0][i] = val * quick_pow(x, n - i, mod) % mod * quick_pow(y, mod - i - 1, mod) % mod;
}
}
for (register int i = 1; i <= maxa; i++){
for (register int j = 1; j <= maxb; j++){
ans[i][j] = ((ans[i][j - 1] - x * ans[i - 1][j] % mod) * inv_val % mod + mod) % mod;
}
}
}
}
for (register int i = 1; i <= q; i++){
printf("%lld\n", ans[a[i]][b[i]]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5688kb
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: 7ms
memory: 28804kb
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: -100
Time Limit Exceeded
input:
1000000000 998244351 998244352 1 5000 5000