結果

問題 No.2345 max(l,r)
ユーザー LeoProLeoPro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define int long long
using 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 int
ModInt(int v) : value(v < 0 ? MOD + v : v) {}
#endif
ModInt 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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0