結果
問題 | No.1193 Penguin Sequence |
ユーザー |
![]() |
提出日時 | 2020-08-22 13:42:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 2,674 bytes |
コンパイル時間 | 1,002 ms |
コンパイル使用メモリ | 86,152 KB |
実行使用メモリ | 12,668 KB |
最終ジャッジ日時 | 2024-10-15 07:58:01 |
合計ジャッジ時間 | 10,351 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#ifndef CLASS_MODINT #define CLASS_MODINT #include <cstdint> template <std::uint32_t mod> class modint { private: std::uint32_t n; public: modint() : n(0) {}; modint(std::int64_t n_) : n((n_ >= 0 ? n_ : mod - (-n_) % mod) % mod) {}; static constexpr std::uint32_t get_mod() { return mod; } std::uint32_t get() const { return n; } bool operator==(const modint& m) const { return n == m.n; } bool operator!=(const modint& m) const { return n != m.n; } modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; } modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; } modint operator+(const modint& m) const { return modint(*this) += m; } modint operator-(const modint& m) const { return modint(*this) -= m; } modint operator*(const modint& m) const { return modint(*this) *= m; } modint inv() const { return (*this).pow(mod - 2); } modint pow(std::uint64_t b) const { modint ans = 1, m = modint(*this); while (b) { if (b & 1) ans *= m; m *= m; b >>= 1; } return ans; } }; #endif // CLASS_MODINT #include <vector> #include <iostream> #include <algorithm> #include <functional> using namespace std; using mint = modint<998244353>; long long inversion(int N, vector<int> A) { vector<int> perm(N); for (int i = 0; i < N; ++i) { perm[i] = i; } sort(perm.begin(), perm.end(), [&](int i, int j) { return A[i] != A[j] ? A[i] > A[j] : i > j; }); long long ans = 0; vector<int> bit(N + 1); for (int i : perm) { for (int j = i; j >= 1; j -= j & (-j)) { ans += bit[j]; } for (int j = i + 1; j <= N; j += j & (-j)) { ++bit[j]; } } return ans; } int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } vector<mint> fact(N + 1), factinv(N + 1); fact[0] = 1; for (int i = 1; i <= N; ++i) fact[i] = fact[i - 1] * i; factinv[N] = fact[N].inv(); for (int i = N; i >= 1; --i) factinv[i - 1] = factinv[i] * i; function<mint(int, int)> comb = [&](int x, int y) { if (x < y || y < 0) return mint(0); return fact[x] * factinv[y] * factinv[x - y]; }; long long p1 = inversion(N, A); vector<int> B = A; B.insert(B.end(), A.begin(), A.end()); long long p2 = inversion(2 * N, B) - p1 * 2; mint ans = 1; mint coeff = 0; long long sum = 0; for (int i = 1; i <= N; ++i) { coeff += mint(p1) * mint(1LL * i * (i - 1) / 2) * mint(1LL * N * (N - 1) / 2).inv(); coeff += mint(p2) * mint(1LL * sum * i) * mint(1LL * N * N).inv(); sum += i; ans *= comb(N, i); } ans *= coeff; cout << ans.get() << endl; return 0; }