結果
問題 | No.2615 ペアの作り方 |
ユーザー |
![]() |
提出日時 | 2024-01-27 17:11:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,612 bytes |
コンパイル時間 | 2,220 ms |
コンパイル使用メモリ | 213,644 KB |
最終ジャッジ日時 | 2025-02-19 00:20:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 WA * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {return '"' + s + '"';}string to_string(const char* s) {return to_string((string) s);}string to_string(bool b) {return (b ? "true" : "false");}string to_string(vector<bool> v) {bool first = true;string res = "{";for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {res += ", ";}first = false;res += to_string(v[i]);}res += "}";return res;}template <size_t N>string to_string(bitset<N> v) {string res = "";for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + v[i]);}return res;}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}#ifdef LOCAL#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endiftemplate <class T> struct Combina {int n;std::vector<T> fact, invfact;Combina() {}Combina(int _n) : n(_n), fact(_n + 1), invfact(_n + 1) {fact[0] = 1;for (int i = 1; i <= n; i++)fact[i] = fact[i - 1] * i;invfact[n] = 1 / fact[n];for (int i = n; i >= 1; i--)invfact[i - 1] = invfact[i] * i;}T binom(int a, int b) {if (a < b || b < 0)return 0;return fact[a] * invfact[b] * invfact[a - b];}long long lucas(long long n, long long m, long long p) {if (n > 0 || m > 0)return lucas(n / p, m / p, p) * lucas(n % p, m % p, p) % p;elsereturn 1ll;}};template <typename T> T mod_inv_in_range(T a, T m) {// assert(0 <= a && a < m);T x = a, y = m;// coeff of a in x and yT vx = 1, vy = 0;while (x) {T k = y / x;y %= x;vy -= k * vx;std::swap(x, y);std::swap(vx, vy);}assert(y == 1);return vy < 0 ? m + vy : vy;}template <typename T> struct extended_gcd_result {T gcd;T coeff_a, coeff_b;};template <typename T> extended_gcd_result<T> extended_gcd(T a, T b) {T x = a, y = b;// coeff of a and b in x and yT ax = 1, ay = 0;T bx = 0, by = 1;while (x) {T k = y / x;y %= x;ay -= k * ax;by -= k * bx;std::swap(x, y);std::swap(ax, ay);std::swap(bx, by);}return {y, ay, by};}template <typename T> T mod_inv(T a, T m) {a %= m;a = a < 0 ? a + m : a;return mod_inv_in_range(a, m);}template <int MOD_> struct modnum {static constexpr int MOD = MOD_;static_assert(MOD_ > 0, "MOD must be positive");private:int v;public:modnum() : v(0) {}modnum(int64_t v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }explicit operator int() const { return v; }friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }friend std::istream& operator >> (std::istream& in, modnum& n) { int64_t v_; in >> v_; n = modnum(v_); return in; }friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }modnum inv() const {modnum res;res.v = mod_inv_in_range(v, MOD);return res;}friend modnum inv(const modnum& m) { return m.inv(); }modnum neg() const {modnum res;res.v = v ? MOD-v : 0;return res;}friend modnum neg(const modnum& m) { return m.neg(); }modnum operator- () const {return neg();}modnum operator+ () const {return modnum(*this);}modnum& operator ++ () {v ++;if (v == MOD) v = 0;return *this;}modnum& operator -- () {if (v == 0) v = MOD;v --;return *this;}modnum& operator += (const modnum& o) {v -= MOD-o.v;v = (v < 0) ? v + MOD : v;return *this;}modnum& operator -= (const modnum& o) {v -= o.v;v = (v < 0) ? v + MOD : v;return *this;}modnum& operator *= (const modnum& o) {v = int(int64_t(v) * int64_t(o.v) % MOD);return *this;}modnum& operator /= (const modnum& o) {return *this *= o.inv();}friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }};template <typename T> T pow(T a, long long b) {assert(b >= 0);T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;}int main() {std::cin.tie(nullptr)->sync_with_stdio(false);using num = modnum<998244353>;int N; std::cin >> N;std::vector<int> X(N), Y(N);std::vector<int> S;for (auto &x : X) std::cin >> x, S.push_back(x);for (auto &x : Y) std::cin >> x, S.push_back(x);std::sort(X.begin(), X.end());std::sort(Y.rbegin(), Y.rend());std::sort(S.begin(), S.end());S.resize(N);std::set<int> hv;hv.insert(S.begin(), S.end());debug(hv);Combina<num> comb(N);int A = 0;for (auto &x : X) A += (hv.count(x) != 0U);int B = N - A;if (A > B) std::swap(A, B);auto sq = [](const num &x) -> num {return num(x * x);};num ans = sq(comb.fact[std::min(A, B)]);int diff = B - A;ans *= comb.binom(B, diff) * sq(diff);std::cout << ans << "\n";}