結果

問題 No.2345 max(l,r)
ユーザー LeoProLeoPro
提出日時 2023-06-09 22:25:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 133 ms / 2,000 ms
コード長 4,954 bytes
コンパイル時間 2,881 ms
コンパイル使用メモリ 225,592 KB
実行使用メモリ 17,684 KB
最終ジャッジ日時 2023-08-30 13:35:02
合計ジャッジ時間 8,229 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 35 ms
4,384 KB
testcase_02 AC 25 ms
4,376 KB
testcase_03 AC 26 ms
4,380 KB
testcase_04 AC 26 ms
4,380 KB
testcase_05 AC 25 ms
4,380 KB
testcase_06 AC 25 ms
4,376 KB
testcase_07 AC 26 ms
4,380 KB
testcase_08 AC 25 ms
4,380 KB
testcase_09 AC 26 ms
4,376 KB
testcase_10 AC 26 ms
4,380 KB
testcase_11 AC 25 ms
4,380 KB
testcase_12 AC 26 ms
4,380 KB
testcase_13 AC 27 ms
4,376 KB
testcase_14 AC 26 ms
4,380 KB
testcase_15 AC 26 ms
4,376 KB
testcase_16 AC 26 ms
4,376 KB
testcase_17 AC 26 ms
4,376 KB
testcase_18 AC 26 ms
4,380 KB
testcase_19 AC 26 ms
4,380 KB
testcase_20 AC 26 ms
4,380 KB
testcase_21 AC 26 ms
4,376 KB
testcase_22 AC 105 ms
14,380 KB
testcase_23 AC 106 ms
14,364 KB
testcase_24 AC 21 ms
6,656 KB
testcase_25 AC 32 ms
8,160 KB
testcase_26 AC 32 ms
6,368 KB
testcase_27 AC 31 ms
7,620 KB
testcase_28 AC 13 ms
7,104 KB
testcase_29 AC 21 ms
7,504 KB
testcase_30 AC 12 ms
6,972 KB
testcase_31 AC 28 ms
8,032 KB
testcase_32 AC 15 ms
6,724 KB
testcase_33 AC 16 ms
5,916 KB
testcase_34 AC 5 ms
5,464 KB
testcase_35 AC 10 ms
6,252 KB
testcase_36 AC 10 ms
5,980 KB
testcase_37 AC 13 ms
5,932 KB
testcase_38 AC 36 ms
10,920 KB
testcase_39 AC 59 ms
10,744 KB
testcase_40 AC 45 ms
8,988 KB
testcase_41 AC 36 ms
10,332 KB
testcase_42 AC 41 ms
8,364 KB
testcase_43 AC 37 ms
7,976 KB
testcase_44 AC 57 ms
10,908 KB
testcase_45 AC 109 ms
17,684 KB
testcase_46 AC 90 ms
13,468 KB
testcase_47 AC 45 ms
10,600 KB
testcase_48 AC 24 ms
8,824 KB
testcase_49 AC 23 ms
6,792 KB
testcase_50 AC 27 ms
7,140 KB
testcase_51 AC 25 ms
6,500 KB
testcase_52 AC 24 ms
6,968 KB
testcase_53 AC 24 ms
6,668 KB
testcase_54 AC 25 ms
6,964 KB
testcase_55 AC 21 ms
6,348 KB
testcase_56 AC 25 ms
7,668 KB
testcase_57 AC 27 ms
8,412 KB
testcase_58 AC 40 ms
6,772 KB
testcase_59 AC 41 ms
6,680 KB
testcase_60 AC 41 ms
8,708 KB
testcase_61 AC 43 ms
8,700 KB
testcase_62 AC 41 ms
7,888 KB
testcase_63 AC 40 ms
7,244 KB
testcase_64 AC 42 ms
7,708 KB
testcase_65 AC 39 ms
6,764 KB
testcase_66 AC 43 ms
7,964 KB
testcase_67 AC 41 ms
7,240 KB
testcase_68 AC 133 ms
6,248 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) { if (k < 0 || k > n) return 0; 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 + n + 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';
}
0