QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#103213 | #2834. Nonsense | Leasier | WA | 42ms | 28760kb | C++14 | 3.3kb | 2023-05-04 19:36:09 | 2023-05-04 19:36:12 |
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[M + 7], 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;
}
}
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){
for (register int i = 0; i <= maxa; i++){
for (register int j = 0; j <= maxb; j++){
ans[i][j] = val[i + j] * quick_pow(x, n - i - j, mod) % 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;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3628kb
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: 42ms
memory: 28760kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
0 1 1
result:
wrong answer 1st lines differ - expected: '381781645', found: '0'