QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#81901 | #2834. Nonsense | AHSFNU_team_0# | WA | 241ms | 102912kb | C++14 | 3.2kb | 2023-02-26 17:31:54 | 2023-02-26 17:31:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std; const int maxn = 5e3 + 5, maxm = 2e5 + 5, mod = 998244353; typedef long long ll;
inline int qpow(int x, int k) { int res = 1; while (k) { if (k & 1) res = (ll)res * x % mod; x = (ll)x * x % mod, k >>= 1; } return res; }
int n, A, B, q, a[maxm], b[maxm], ma, mb;
int C[maxn << 1], F1[maxn << 1], F2[maxn << 1], C_[maxn << 1];
// inline int Calc(int a, int b, int i)
// {
// return (ll)F2[i] * qpow(F2[a], )
// }
int f[maxn][maxn];
int main()
{
for (int i = F2[0] = 1; i < maxn << 1; i++) F2[i] = (ll)F2[i - 1] * i % mod;
while (~scanf("%d%d%d%d", &n, &A, &B, &q))
{
ma = mb = 0;
for (int i = 1; i <= q; i++) scanf("%d%d", a + i, b + i), ma = max(ma, a[i]), mb = max(mb, b[i]);
for (int i = C[0] = 1; i <= ma + mb; i++) C[i] = (ll)C[i - 1] * (n - i + 1) % mod * qpow(i, mod - 2) % mod;
for (int i = C_[0] = 1; i <= ma + mb + 1; i++) C_[i] = (ll)C_[i - 1] * (n - i + 2) % mod * qpow(i, mod - 2) % mod;
// for (int i = 0; i <= ma + mb; i++) cerr << C[i] << ' '; cerr << endl;
if (A == 0 && B != 0)
{
F1[0] = n;
for (int i = 1; i <= ma + mb; i++) F1[i] = (ll)F1[i - 1] * (n - i) % mod;
for (int i = 1; i <= q; i++)
{
int Ans = (ll)F1[a[i] + b[i] - 1] * qpow(F1[a[i] - 1], mod - 2) % mod * qpow(F2[b[i]], mod - 2) % mod * qpow(B, n - a[i] - a[i]) % mod;
printf("%d\n", (Ans + mod) % mod);
}
continue;
}
if (A != 0 && B == 0)
{
F1[0] = n;
for (int i = 1; i <= ma + mb; i++) F1[i] = (ll)F1[i - 1] * (n - i) % mod;
for (int i = 1; i <= q; i++)
{
int Ans = (ll)F1[a[i] + b[i] - 1] * qpow(F1[b[i] - 1], mod - 2) % mod * qpow(F2[a[i]], mod - 2) % mod * qpow(A, n - a[i] - b[i]) % mod;
printf("%d\n", (Ans + mod) % mod);
}
continue;
}
if (A == 0 && B == 0)
{
for (int i = 1; i <= q; i++) printf("%d\n", int(a[i] + b[i] == n));
continue;
}
if (A == B)
{
for (int i = 1; i <= q; i++)
{
int Ans = (ll)qpow(A, n - a[i] - b[i]) * C_[a[i] + b[i] + 1] % mod;
printf("%d\n", (Ans + mod) % mod);
}
continue;
}
for (int i = 0; i <= ma; i++) for (int j = 0; j <= mb; j++) f[i][j] = 0;
for (int j = 0, K = qpow(B, n + 1); j <= mb; j++) f[0][j] = (ll)C_[j] * K % mod;
for (int i = 0, K = qpow(A, n + 1); i <= ma; i++) f[i][0] = (f[i][0] - (ll)C_[i] * K) % mod;
int K = qpow(B - A, mod - 2);
for (int i = 0; i <= ma; i++) for (int j = 0; j <= mb; j++)
{
f[i][j] = (f[i][j] - (ll)B * (j ? f[i][j - 1] : 0) + (ll)A * (i ? f[i - 1][j] : 0)) % mod * K % mod;
}
for (int i = 1; i <= q; i++)
{
// int Ans = f[a[i]][b[i]];
int Ans = (ll)f[a[i]][b[i]] * qpow((ll)qpow(A, a[i]) * qpow(B, b[i]) % mod, mod - 2) % mod;
printf("%d\n", (Ans + mod) % mod);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5528kb
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: 1ms
memory: 5728kb
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: 241ms
memory: 102912kb
input:
1000000000 998244351 998244352 1 5000 5000
output:
663228915
result:
ok single line: '663228915'
Test #4:
score: -100
Wrong Answer
time: 78ms
memory: 3552kb
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:
wrong answer 1602nd lines differ - expected: '532829070', found: '134827574'