結果
問題 | No.2345 max(l,r) |
ユーザー | LeoPro |
提出日時 | 2023-06-09 22:20:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,920 bytes |
コンパイル時間 | 2,789 ms |
コンパイル使用メモリ | 218,660 KB |
実行使用メモリ | 14,568 KB |
最終ジャッジ日時 | 2025-01-02 03:31:26 |
合計ジャッジ時間 | 6,705 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 26 ms
6,816 KB |
testcase_07 | AC | 25 ms
6,816 KB |
testcase_08 | AC | 25 ms
6,820 KB |
testcase_09 | AC | 25 ms
6,816 KB |
testcase_10 | AC | 26 ms
6,820 KB |
testcase_11 | AC | 26 ms
6,816 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 27 ms
6,820 KB |
testcase_18 | AC | 26 ms
6,816 KB |
testcase_19 | AC | 27 ms
6,816 KB |
testcase_20 | AC | 26 ms
6,816 KB |
testcase_21 | AC | 28 ms
6,816 KB |
testcase_22 | AC | 73 ms
12,288 KB |
testcase_23 | AC | 72 ms
12,160 KB |
testcase_24 | AC | 18 ms
6,820 KB |
testcase_25 | AC | 29 ms
8,272 KB |
testcase_26 | AC | 29 ms
6,820 KB |
testcase_27 | AC | 28 ms
7,548 KB |
testcase_28 | WA | - |
testcase_29 | AC | 17 ms
6,816 KB |
testcase_30 | AC | 10 ms
6,820 KB |
testcase_31 | AC | 20 ms
6,816 KB |
testcase_32 | AC | 12 ms
6,820 KB |
testcase_33 | AC | 12 ms
6,816 KB |
testcase_34 | AC | 4 ms
6,816 KB |
testcase_35 | AC | 8 ms
6,820 KB |
testcase_36 | AC | 10 ms
6,820 KB |
testcase_37 | AC | 10 ms
6,820 KB |
testcase_38 | AC | 30 ms
7,808 KB |
testcase_39 | AC | 49 ms
7,808 KB |
testcase_40 | AC | 37 ms
6,820 KB |
testcase_41 | AC | 29 ms
7,552 KB |
testcase_42 | AC | 31 ms
6,816 KB |
testcase_43 | AC | 29 ms
6,820 KB |
testcase_44 | AC | 49 ms
7,936 KB |
testcase_45 | AC | 84 ms
14,568 KB |
testcase_46 | AC | 72 ms
10,240 KB |
testcase_47 | AC | 36 ms
7,680 KB |
testcase_48 | AC | 23 ms
8,676 KB |
testcase_49 | AC | 22 ms
6,816 KB |
testcase_50 | AC | 25 ms
7,024 KB |
testcase_51 | AC | 24 ms
6,820 KB |
testcase_52 | AC | 21 ms
6,984 KB |
testcase_53 | AC | 20 ms
6,816 KB |
testcase_54 | AC | 23 ms
7,172 KB |
testcase_55 | AC | 19 ms
6,820 KB |
testcase_56 | AC | 22 ms
8,640 KB |
testcase_57 | AC | 25 ms
8,652 KB |
testcase_58 | AC | 36 ms
6,848 KB |
testcase_59 | AC | 36 ms
6,820 KB |
testcase_60 | AC | 36 ms
8,020 KB |
testcase_61 | AC | 39 ms
7,868 KB |
testcase_62 | AC | 38 ms
7,432 KB |
testcase_63 | RE | - |
testcase_64 | AC | 42 ms
7,996 KB |
testcase_65 | AC | 40 ms
7,048 KB |
testcase_66 | AC | 40 ms
7,424 KB |
testcase_67 | AC | 39 ms
7,052 KB |
testcase_68 | AC | 132 ms
6,820 KB |
ソースコード
#ifdef LOCAL#define _GLIBCXX_DEBUG#endif#include <bits/stdc++.h>#define int long longusing namespace std;using ll = long long;void solve();template<typename ...Args>void println(Args... args) {apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));cout << '\n';}int32_t main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);int t = 1;cin >> t;for (int tc = 0; tc < t; ++tc) {solve();}return 0;}template<int32_t MOD>struct ModInt {int value;ModInt() : value(0) {}ModInt(ll v) : value(v % MOD) { if (value < 0) value += MOD; }#ifndef intModInt(int v) : value(v < 0 ? MOD + v : v) {}#endifModInt operator+=(ModInt m) {value += m.value;if (value >= MOD) value -= MOD;return value;}ModInt operator-=(ModInt m) {value -= m.value;if (value < 0) value += MOD;return value;}ModInt operator*=(ModInt m) {value = (value * 1LL * m.value) % MOD;return value;}ModInt power(int exp) const {if (exp == 0) return 1;ModInt res = (exp & 1 ? value : 1);ModInt half = power(exp >> 1);return res * half * half;}ModInt operator/=(ModInt m) { return *this *= m.power(MOD - 2); }friend std::istream &operator>>(std::istream &is, ModInt &m) {is >> m.value;return is;}friend std::ostream &operator<<(std::ostream &os, const ModInt &m) {os << m.value;return os;}explicit operator int32_t() const { return value; }explicit operator ll() const { return value; }static int32_t mod() { return MOD; }};template<int32_t MOD>ModInt<MOD> operator+(ModInt<MOD> a, ModInt<MOD> b) { return a += b; }template<int32_t MOD>ModInt<MOD> operator-(ModInt<MOD> a, ModInt<MOD> b) { return a -= b; }template<int32_t MOD>ModInt<MOD> operator*(ModInt<MOD> a, ModInt<MOD> b) { return a *= b; }template<int32_t MOD>ModInt<MOD> operator/(ModInt<MOD> a, ModInt<MOD> b) { return a /= b; }template<int32_t MOD>ModInt<MOD> operator==(ModInt<MOD> a, ModInt<MOD> b) { return (int32_t) a == (int32_t) b; }template<int32_t MOD>ModInt<MOD> operator!=(ModInt<MOD> a, ModInt<MOD> b) { return (int32_t) a != (int32_t) b; }using mint = ModInt<998244353>;//using mint = ModInt<(int32_t)(1e9 + 7)>;vector<mint> f{1}, inv{1};void precomputeFactorials(int size) {if (f.size() >= size) return;int old = f.size();f.resize(size, 0);inv.resize(size, 0);for (int i = old; i < size; ++i) f[i] = f[i - 1] * mint(i);inv[size - 1] = mint(1) / f[size - 1];for (int i = size - 1; i >= old; --i) inv[i - 1] = inv[i] * mint(i);}mint binom(int n, int k) { return f[n] * inv[k] * inv[n - k]; }mint check(const vector<int> &row, map<int, int> cnt) {int s = accumulate(row.begin(), row.end(), 0LL);int t = 0;vector<int> lf(row.size()), rg(row.size());for (int i = 0; i < row.size(); ++i) {lf[i] = t;t += row[i];s -= row[i];rg[i] = s;}mint res = 1;for (int i = 0; i < row.size(); ++i) {int mx = max(lf[i], rg[i]);if (cnt[mx] < row[i]) return 0;res *= binom(cnt[mx], row[i]);cnt[mx] -= row[i];}for (auto [k, v] : cnt) {if (v != 0) return 0;}return res;}void solve() {int n, m;cin >> n >> m;precomputeFactorials(m + 100);vector<int> a(n);for (int &x: a) cin >> x;map<int, int> t;for (int x: a) t[x]++;vector<pair<int, int>> cnt(t.begin(), t.end());reverse(cnt.begin(), cnt.end());mint ans = 1;vector<int> lfcur, rgcur;vector<int> lf, rg;int lfs = 0, rgs = 0;for (auto &[mx, cn]: cnt) {int mn = n - mx;if (cn + lfs == mn) {lfcur.push_back(cn);lfs += cn;} else if (cn + rgs == mn) {rgcur.push_back(cn);rgs += cn;} else if (cn + lfs + rgs == mn + mn) {lfcur.push_back(mn - lfs);lfs += mn - lfs;rgcur.push_back(mn - rgs);rgs += mn - rgs;} else {return println(0);}if (lfs == rgs) {if (lfcur != rgcur) ans *= 2;for (int x: lfcur) lf.push_back(x);lfcur.clear();for (int x: rgcur) rg.push_back(x);rgcur.clear();}}auto concat = lfcur;for (int j = (int) rgcur.size() - 1; j >= 0; --j) concat.push_back(rgcur[j]);auto rconcat = concat;reverse(rconcat.begin(), rconcat.end());if (concat != rconcat) ans *= 2;for (int x: concat) lf.push_back(x);reverse(rg.begin(), rg.end());for (int x: rg) lf.push_back(x);mint o = check(lf, t);cout << ans * binom(m, lf.size()) * o << '\n';}