結果
問題 | No.1963 Subset Mex |
ユーザー | RiverHamster |
提出日時 | 2022-07-13 01:18:59 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,403 bytes |
コンパイル時間 | 538 ms |
コンパイル使用メモリ | 55,144 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-23 23:24:54 |
合計ジャッジ時間 | 1,771 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
ソースコード
#include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #include <numeric> #include <vector> #include <cassert> using namespace std; using ll = long long; using ull = unsigned long long; #define LOG(f...) fprintf(stderr, f) // #define DBG(f...) printf(f) #define DBG(f...) void() #define all(cont) begin(cont), end(cont) const int N = 105; const int M = 998244353; void inc(int &x, int y) { if ((x += y) >= M) x -= M; } int a[N]; int dp[2][N][N]; int cost[N]; int main() { freopen("normal.in", "r", stdin); freopen("normal.out", "w", stdout); int n; scanf("%d", &n); for (int i = 0, x; i < n; ++i) scanf("%d", &x), ++a[x]; int (*f)[N] = dp[0], (*g)[N] = dp[1]; f[0][0] = 1; int ans = (a[0] != n) + n, les = n; for (int i = 100; i; --i, swap(f, g)) { DBG("i = %d\n", i); memset(g, 0, sizeof(dp[0])); les -= a[i]; for (int req = 0, li = n / (i + 1); req <= li; ++req) for (int cnt = 0, li = a[i] + n / i; cnt <= li; ++cnt) { auto tf = [&](int r, int e, int val) { if (r <= n && e <= n) inc(g[r][e], val); }; int c = req + cnt; if (c <= a[i]) { for (int ext = 0; ext <= n; ++ext) tf(req, ext + a[i] - c, f[req][ext]); } else { for (int ext = 0; ext <= n; ++ext) tf(req + c - a[i], ext, f[req][ext]); } } for (int c = 1; c <= a[i]; ++c) for (int ext = 0; ext <= n; ++ext) { int e = ext + a[i] - c; int c0 = e + 1 + a[0], req = 1; for (int j = i - 1; j; --j) { if (a[j] >= req) c0 += a[j] - req; else req += req - a[j]; if (req > n) break; } DBG("e = %d : %d * %d\n", e, f[0][ext], e + les + (req <= c0)); DBG("req = %d c0 = %d\n", req, c0); ans = (ans + (ll)f[0][ext] * (e + les + (req <= c0))) % M; if (!ext && les == a[0] && c == a[i] && (les || (req <= c0 && !a[0]))) ans = (ans + M - 1) % M; } for (int req = 0; req <= n; ++req) for (int ext = 0; ext <= n; ++ext) if (g[req][ext]) DBG("g[%d][%d] = %d\n", req, ext, g[req][ext]); DBG("ans = %d\n", ans); } for (int req = 1; req <= n; ++req) for (int ext = max(0, req - a[0]); ext <= n; ++ext) ans = (ans + (ll)f[req][ext] * (ext + a[0] - req + 1)) % M; printf("%d\n", ans); }