結果
問題 | No.2616 中央番目の中央値 |
ユーザー |
![]() |
提出日時 | 2024-01-27 07:42:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 4,536 bytes |
コンパイル時間 | 3,418 ms |
コンパイル使用メモリ | 250,312 KB |
実行使用メモリ | 10,328 KB |
最終ジャッジ日時 | 2024-09-28 09:34:48 |
合計ジャッジ時間 | 5,213 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>#include <vector>namespace nono {template <class T>class FenwickTree {public:FenwickTree(int size = 0): size_(size), data_(size_ + 1) {}void add(int i, const T& v) {for (++i; i <= size_; i += i & -i) {data_[i] += v;}}T sum(int i) const {T result{};for (; i > 0; i -= i & -i) {result += data_[i];}return result;}T sum(int l, int r) const {return sum(r) - sum(l);}private:int size_;std::vector<T> data_;};} // namespace nono#include <iostream>namespace nono {namespace internal {constexpr bool is_prime(unsigned long long n) {for (unsigned long long i = 2; i * i <= n; i++) {if (n % i == 0) return false;}return true;}} // namespace internaltemplate <unsigned long long MOD = 998244353>class Modint {public:static_assert(internal::is_prime(MOD));constexpr Modint(unsigned long long value = 0): value_(value % MOD) {}constexpr Modint pow(long long exp) const {Modint result(1);Modint base(*this);while (exp > 0) {if (exp & 1) {result *= base;}base *= base;exp >>= 1;}return result;}constexpr Modint inv() const {return pow(MOD - 2);}void set(unsigned long long value) {if (value >= MOD) value %= MOD;value_ = value;}unsigned long long get() const {return value_;}friend constexpr bool operator==(const Modint lhs, const Modint rhs) {return lhs.value_ == rhs.value_;}constexpr Modint& operator+=(const Modint other) {this->value_ += other.value_;if (this->value_ >= MOD) this->value_ -= MOD;return *this;}constexpr Modint& operator-=(const Modint other) {this->value_ += MOD - other.value_;if (this->value_ >= MOD) this->value_ -= MOD;return *this;}constexpr Modint& operator*=(const Modint other) {this->value_ *= other.value_;if (this->value_ >= MOD) this->value_ %= MOD;return *this;}constexpr Modint& operator/=(const Modint other) {return *this *= other.inv();}constexpr friend Modint operator+(const Modint lhs, const Modint rhs) {return Modint(lhs) += rhs;}constexpr friend Modint operator-(const Modint lhs, const Modint rhs) {return Modint(lhs) -= rhs;}constexpr friend Modint operator*(const Modint lhs, const Modint rhs) {return Modint(lhs) *= rhs;}constexpr friend Modint operator/(const Modint lhs, const Modint rhs) {return Modint(lhs) /= rhs;}friend std::istream& operator>>(std::istream& stream, Modint& mint) {unsigned long long value;stream >> value;mint.set(value);return stream;}friend std::ostream& operator<<(std::ostream& stream, Modint mint) {stream << mint.get();return stream;}private:unsigned long long value_;};using Modint998244353 = Modint<998244353>;using Modint1000000007 = Modint<1000000007>;} // namespace nonovoid solve() {using Mint = nono::Modint998244353;constexpr int N = 300005;std::array<Mint, N> fact, fact_inv;fact.fill(1);fact_inv.fill(1);for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i;fact_inv[N - 1] = fact[N - 1].inv();for (int i = N - 1; i > 0; i--) fact_inv[i - 1] = fact_inv[i] * i;auto binom = [&](int n, int k) {return fact.at(n) * fact_inv.at(k) * fact_inv.at(n - k);};int n;std::cin >> n;std::vector<int> p(n);for (int i = 0; i < n; i++) std::cin >> p[i];for (int i = 0; i < n; i++) p[i]--;nono::FenwickTree<int> fenwick(n);Mint ans = 0;for (int i = 0; i < n; i++) {int small_left = fenwick.sum(0, p[i]);int big_left = i - small_left;int small_right = p[i] - small_left;int big_right = (n - p[i] - 1) - big_left;Mint left = binom(small_left + big_right, small_left);Mint right = binom(small_right + big_left, small_right);ans += left * right;fenwick.add(p[i], 1);}std::cout << ans << '\n';}int main() {std::cin.tie(0)->sync_with_stdio(0);std::cout << std::fixed << std::setprecision(16);int t = 1;while (t--) solve();}