QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618220#2834. NonsensehcywoiWA 216ms101796kbC++235.9kb2024-10-06 19:54:562024-10-06 19:54:57

Judging History

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

  • [2024-10-06 19:54:57]
  • 评测
  • 测评结果:WA
  • 用时:216ms
  • 内存:101796kb
  • [2024-10-06 19:54:56]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
template<class T>
T qmi(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<int P>
struct modint {
    int x;
    constexpr modint() : x{} {}
    constexpr modint(i64 x) : x{norm(x % getmod())} {}

    static int mod;
    constexpr static int getmod() {
        if (P > 0) {
            return P;
        } else {
            return mod;
        }
    }
    constexpr static void setmod(int m) {
        mod = m;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getmod();
        }
        if (x >= getmod()) {
            x -= getmod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr modint operator-() const {
        modint res;
        res.x = norm(getmod() - x);
        return res;
    }
    constexpr modint inv() const {
        assert(x != 0);
        return qmi(*this, getmod() - 2);
    }
    constexpr modint &operator*= (modint v) & {
        x = 1LL * x * v.x % getmod();
        return *this;
    }
    constexpr modint &operator+= (modint v) & {
        x = norm(x + v.x);
        return *this;
    }
    constexpr modint &operator-= (modint v) & {
        x = norm(x - v.x);
        return *this;
    }
    constexpr modint &operator/= (modint v) & {
        return *this *= v.inv();
    }
    friend constexpr modint operator- (modint a, modint b) {
        modint res = a;
        res -= b;
        return res;
    }
    friend constexpr modint operator+ (modint a, modint b) {
        modint res = a;
        res += b;
        return res;
    }
    friend constexpr modint operator* (modint a, modint b) {
        modint res = a;
        res *= b;
        return res;
    }
    friend constexpr modint operator/ (modint a, modint b) {
        modint res = a;
        res /= b;
        return res;
    }
    friend constexpr std::istream &operator>> (std::istream& is, modint& a) {
        i64 v;
        is >> v;
        a = modint(v);
        return is;
    }
    friend constexpr std::ostream &operator<< (std::ostream& os, const modint& a) {
        return os << a.val();
    }
    friend constexpr bool operator== (modint a, modint b) {
        return a.val() == b.val();
    }
    friend constexpr bool operator!= (modint a, modint b) {
        return a.val() != b.val();
    }
};

constexpr int P = 998244353;
using mint = modint<P>;

struct Comb {
    int n;
    std::vector<mint> fact;
    std::vector<mint> invefact;
    std::vector<mint> inve;

    Comb() : n{0}, fact{1}, invefact{1}, inve{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        fact.resize(m + 1);
        invefact.resize(m + 1);
        inve.resize(m + 1);
        
        for (int i = n + 1; i <= m; i ++ ) {
            fact[i] = fact[i - 1] * i;
        }
        invefact[m] = fact[m].inv();
        for (int i = m; i > n; i -- ) {
            invefact[i - 1] = invefact[i] * i;
            inve[i] = invefact[i] * fact[i - 1];
        }
        n = m;
    }
    
    mint fac(int m) {
        if (m > n) init(2 * m);
        return fact[m];
    }
    mint invfac(int m) {
        if (m > n) init(2 * m);
        return invefact[m];
    }
    mint inv(int m) {
        if (m > n) init(2 * m);
        return inve[m];
    }
    mint binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

mint f[5005][5005];

int main() {
    // freopen("count.in", "r", stdin);
    // freopen("count.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, x, y, q;
    while (std::cin >> n >> x >> y >> q) {
        n ++ ;

        int N = 0;
        std::vector<int> a(q), b(q);
        for (int i = 0; i < q; i ++ ) {
            std::cin >> a[i] >> b[i];
            if (x != y) {
                N = std::max({N, a[i], b[i]});
            } else {
                N = std::max(N, a[i] + b[i] + 1);
            }
        }

        std::vector<mint> sx(N + 1), sy(N + 1);
        for (int i = 0; i <= N; i ++ ) {
            sx[i] = qmi(mint(x), n - i);
            sy[i] = qmi(mint(y), n - i);
        }

        std::vector<mint> down(N + 1);
        down[0] = 1;
        for (int i = 1; i <= N; i ++ ) {
            down[i] = down[i - 1] * (n - i + 1);
        }

        auto binom = [&](int m) -> mint {
            return down[m] * comb.invfac(m);
        };

        if (x == y) {
            for (int i = 0; i < q; i ++ ) {
                if (x == 0) {
                    std::cout << (a[i] == b[i]) << "\n";
                } else {
                    std::cout << binom(a[i] + b[i] + 1) * sx[a[i] + b[i] + 1] << "\n";
                }
            }
            continue;
        }
        const mint inv = mint(y - x).inv();

        for (int a = 0; a <= N; a ++ ) {
            for (int b = 0; b <= N; b ++ ) {
                if (a == 0 && b == 0) {
                    f[a][b] = (binom(b) * sy[b] - binom(a) * sx[a]) * inv;
                } else if (a == 0) {
                    f[a][b] = (binom(b) * sy[b] - f[a][b - 1]) * inv;
                } else if (b == 0) {
                    f[a][b] = (f[a - 1][b] - binom(a) * sx[a]) * inv;
                } else {
                    f[a][b] = (f[a - 1][b] - f[a][b - 1]) * inv;
                }
            }
        }

        for (int i = 0; i < q; i ++ ) {
            std::cout << f[a[i]][b[i]] << "\n";
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

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: 8ms
memory: 22692kb

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: 216ms
memory: 101796kb

input:

1000000000 998244351 998244352 1
5000 5000

output:

663228915

result:

ok single line: '663228915'

Test #4:

score: -100
Wrong Answer
time: 20ms
memory: 3640kb

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 30605th lines differ - expected: '0', found: '1'