QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#81901#2834. NonsenseAHSFNU_team_0#WA 241ms102912kbC++143.2kb2023-02-26 17:31:542023-02-26 17:31:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-26 17:31:57]
  • 评测
  • 测评结果:WA
  • 用时:241ms
  • 内存:102912kb
  • [2023-02-26 17:31:54]
  • 提交

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'