QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#454587 | #8815. Space Station | rgnerdplayer | WA | 0ms | 3732kb | C++20 | 4.1kb | 2024-06-25 04:53:24 | 2024-06-25 04:53:25 |
Judging History
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'