QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#454587#8815. Space StationrgnerdplayerWA 0ms3732kbC++204.1kb2024-06-25 04:53:242024-06-25 04:53:25

Judging History

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

  • [2024-07-30 16:51:06]
  • hack成功,自动添加数据
  • (/hack/760)
  • [2024-06-25 04:53:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3732kb
  • [2024-06-25 04:53:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

template <int P>
struct Modint {
    int v;

    constexpr Modint() : v(0) {}
    constexpr Modint(i64 v_) : v(v_ % P) {
        if (v < 0) {
            v += P;
        }
    }
    constexpr explicit operator int() const { return v; }
    constexpr friend ostream& operator<<(ostream &out, Modint n) {
        return out << int(n);
    }
    constexpr friend istream& operator>>(istream &in, Modint &n) {
        i64 v;
        in >> v;
        n = Modint(v);
        return in;
    }

    constexpr friend bool operator==(Modint a, Modint b) {
        return a.v == b.v;
    }
    constexpr friend bool operator!=(Modint a, Modint b) {
        return a.v != b.v;
    }

    constexpr Modint operator-() {
        Modint res;
        res.v = v ? P - v : 0;
        return res;
    }

    constexpr Modint& operator++() {
        v++;
        if (v == P) v = 0;
        return *this;
    }
    constexpr Modint& operator--() {
        if (v == 0) v = P;
        v--;
        return *this;
    }
    constexpr Modint& operator+=(Modint o) {
        v -= P - o.v;
        v = (v < 0) ? v + P : v;
        return *this;
    }
    constexpr Modint& operator-=(Modint o) {
        v -= o.v;
        v = (v < 0) ? v + P : v;
        return *this;
    }
    constexpr Modint& operator*=(Modint o) {
        v = 1LL * v * o.v % P;
        return *this;
    }
    constexpr Modint& operator/=(Modint o) { return *this *= o.inv(); }

    constexpr friend Modint operator++(Modint &a, int) {
        Modint r = a;
        ++a;
        return r;
    }
    constexpr friend Modint operator--(Modint &a, int) {
        Modint r = a;
        --a;
        return r;
    }

    constexpr friend Modint operator+(Modint a, Modint b) {
        return Modint(a) += b;
    }
    constexpr friend Modint operator-(Modint a, Modint b) {
        return Modint(a) -= b;
    }
    constexpr friend Modint operator*(Modint a, Modint b) {
        return Modint(a) *= b;
    }
    constexpr friend Modint operator/(Modint a, Modint b) {
        return Modint(a) /= b;
    }

    constexpr Modint qpow(i64 p) {
        Modint res = 1, x = v;
        while (p > 0) {
            if (p & 1) { res *= x; }
            x *= x;
            p >>= 1;
        }
        return res;
    }
    constexpr Modint inv() {
        return qpow(P - 2);
    }
};

constexpr int P = 998244353;
using Mint = Modint<P>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    auto solve = [&]() {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int tot = accumulate(a.begin(), a.end(), 0);

        vector dp(n + 1, vector<Mint>(tot + 1));
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            vector ndp(n + 1, vector<Mint>(tot + 1));
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k + a[i] <= tot; k++) {
                    ndp[j][k] += dp[j][k];
                    ndp[j + 1][k + a[i]] += dp[j][k];
                }
            }
            dp = move(ndp);
        }

        vector<Mint> fact(n + 1), inv(n + 1), ifact(n + 1);
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }
        ifact[n] = fact[n].inv();
        for (int i = n; i > 0; i--) {
            inv[i] = ifact[i] * ifact[i - 1];
            ifact[i - 1] = ifact[i] * i;
        }

        Mint ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= tot; j++) {
                Mint res = dp[i][j] * ifact[n] * fact[i] * fact[n - i];
                if (m * (n - i) <= (tot - j)) {
                    res *= m;
                } else {
                    res *= tot - j;
                    res *= inv[n - i];
                }
                ans += res;
            }
        }

        cout << ans << '\n';
    };
    
    solve();
    
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3732kb

input:

3 3
2 3 4

output:

7

result:

wrong answer 1st numbers differ - expected: '499122185', found: '7'