結果
問題 | No.1963 Subset Mex |
ユーザー |
![]() |
提出日時 | 2022-05-27 23:13:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,832 bytes |
コンパイル時間 | 1,107 ms |
コンパイル使用メモリ | 90,324 KB |
最終ジャッジ日時 | 2025-01-29 16:19:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 23 WA * 3 |
ソースコード
// たすけて~#pragma warning(disable : 4146)#include <algorithm>#include <cassert>#include <cstddef>#include <cstdint>#include <iomanip>#include <ios>#include <iostream>#include <utility>#include <vector>namespace n91 {using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;using f64 = double;struct rep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr rep(const usize f, const usize l) noexcept: f(std::min(f, l)), l(l) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};struct revrep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr revrep(const usize f, const usize l) noexcept: f(l - 1), l(std::min(f, l) - 1) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) noexcept {return a < b ? b - a : a - b;}template <class T> void chmin(T &a, const T &b) noexcept {if (b < a)a = b;}template <class T> void chmax(T &a, const T &b) noexcept {if (a < b)a = b;}template <class F> class rec_lambda {F f;public:rec_lambda(F &&f_) : f(std::forward<F>(f_)) {}template <class... Args> auto operator()(Args &&... args) const {return f(*this, std::forward<Args>(args)...);}};template <class T> T scan() {T ret;std::cin >> ret;return ret;}constexpr char eoln = '\n';i64 floor_div(const i64 n, const i64 d) {assert(d != 0);return n / d - static_cast<i64>((n ^ d) < 0 && n % d != 0);}i64 ceil_div(const i64 n, const i64 d) {assert(d != 0);return n / d + static_cast<i64>((n ^ d) >= 0 && n % d != 0);}#ifdef N91_LOCAL#define OJ_LOCAL(a, b) b#else#define OJ_LOCAL(a, b) a#endif} // namespace n91#include <atcoder/modint>namespace n91 {void main_() {using mint = atcoder::modint998244353;static constexpr usize MAX = OJ_LOCAL(100, 100);const usize n = scan<usize>();std::vector<usize> s(MAX + 1, 0);for (const usize i : rep(0, n)) {s[scan<usize>()]++;}mint ans = 0;{auto dp = md_vec(n + 1, n + 1, mint());dp[0][0] = 1;for (const usize i : revrep(1, MAX + 1)) {auto nx = md_vec(n + 1, n + 1, mint());for (const usize z : rep(0, n + 1)) {for (const usize r : rep(0, n + 1)) {if (dp[z][r].val() == 0) {continue;}for (const usize c : rep(0, n + 1)) {if (c + r <= s[i]) {nx[z + (s[i] - c - r)][r] += dp[z][r];} else if (r + (c + r - s[i]) <= n) {nx[z][r + (c + r - s[i])] += dp[z][r];}}}}dp = std::move(nx);}for (const usize z : rep(0, n + 1)) {for (const usize r : rep(0, n + 1)) {if (z + s[0] >= r) {ans += (z + s[0] - r + 1) * dp[z][r];}}}}{for (const usize min : rep(1, MAX + 1)) {if (s[min] == 0) {continue;}std::vector<mint> dp(n + 1, 0);for (const usize c : rep(1, s[min] + 1)) {dp[c] = 1;}for (const usize i : rep(min + 1, MAX + 1)) {std::vector<mint> nx(n + 1, 0);for (const usize c : rep(0, s[i] + 1)) {for (const usize j : rep(c, n + 1)) {nx[j] += dp[j - c];}}dp = std::move(nx);}usize r = 1;for (const usize i : revrep(1, min)) {r -= std::min(r, s[i]);r *= 2;chmin(r, n + 1);}r -= std::min(r, s[0]);for (const usize j : rep(0, n + 1)) {if (j < r) {ans -= dp[j];}}}}if (s[0] == 0 && s[1] == 0) {ans += 1;}ans -= 1;std::cout << ans.val() << eoln;}} // namespace n91int main() {//*std::ios::sync_with_stdio(false);std::cin.tie(nullptr);//*/std::cout << std::fixed << std::setprecision(20);n91::main_();return 0;}