結果
問題 | No.2250 Split Permutation |
ユーザー |
👑 |
提出日時 | 2023-03-17 21:34:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 3,000 ms |
コード長 | 13,850 bytes |
コンパイル時間 | 1,871 ms |
コンパイル使用メモリ | 204,748 KB |
最終ジャッジ日時 | 2025-02-11 12:40:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#line 1 "A.cpp"// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;template <class T>using pq = priority_queue<T>;template <class T>using qp = priority_queue<T, vector<T>, greater<T>>;#define vec(T, A, ...) vector<T> A(__VA_ARGS__);#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));#ifndef RIN__LOCAL#define endl "\n"#endif#define spa ' '#define len(A) A.size()#define all(A) begin(A), end(A)#define fori1(a) for(ll _ = 0; _ < (a); _++)#define fori2(i, a) for(ll i = 0; i < (a); i++)#define fori3(i, a, b) for(ll i = (a); i < (b); i++)#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))#define overload4(a, b, c, d, e, ...) e#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)template <typename T>vector<tuple<ll, T>> ENUMERATE(vector<T> &A, ll s = 0){vector<tuple<ll, T>> ret(A.size());for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};return ret;}vector<tuple<ll, char>> ENUMERATE(string &A, ll s = 0){vector<tuple<ll, char>> ret(A.size());for(int i = 0; i < A.size(); i++) ret[i] = {i + s, A[i]};return ret;}#define enum1(A) fori(A.size())#define enum2(a, A) for(auto a:A)#define enum3(i, a, A) for(auto&& [i, a]: ENUMERATE(A))#define enum4(i, a, A, s) for(auto&& [i, a]: ENUMERATE(A, s))#define enum(...) overload4(__VA_ARGS__, enum4, enum3, enum2, enum1)(__VA_ARGS__)template <typename T, typename S>vector<tuple<T, S>> ZIP(vector<T> &A, vector<S> &B){int n = min(A.size(), B.size());vector<tuple<T, S>> ret(n);for(int i = 0; i < n; i++) ret[i] = {A[i], B[i]};return ret;}template <typename T, typename S>vector<tuple<ll, T, S>> ENUMZIP(vector<T> &A, vector<S> &B, ll s = 0){int n = min(A.size(), B.size());vector<tuple<ll, T, S>> ret(n);for(int i = 0; i < n; i++) ret[i] = {i + s, A[i], B[i]};return ret;}#define zip4(a, b, A, B) for(auto&& [a, b]: ZIP(A, B))#define enumzip5(i, a, b, A, B) for(auto&& [i, a, b]: ENUMZIP(A, B))#define enumzip6(i, a, b, A, B, s) for(auto&& [i, a, b]: ENUMZIP(A, B, s))#define overload6(a, b, c, d, e, f, g, ...) g#define zip(...) overload6(__VA_ARGS__, enumzip6, enumzip5, zip4, _, _, _)(__VA_ARGS__)vector<char> stoc(string &S){int n = S.size();vector<char> ret(n);for(int i = 0; i < n; i++) ret[i] = S[i];return ret;}#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);#define VEC(T, A, n) vector<T> A(n); inp(A);#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);const ll MOD1 = 1000000007;const ll MOD9 = 998244353;template<class T> auto min(const T& a){return *min_element(all(a));}template<class T> auto max(const T& a){return *max_element(all(a));}template <class T, class S>auto clamp(T &a, const S &l, const S &r) {return (a > r ? r : a < l ? l : a);}template <class T, class S>inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S>inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}template <class T, class S>inline bool chclamp(T &a, const S &l, const S &r) {auto b = clamp(a, l, r);return (a != b ? a = b, 1 : 0);}void FLUSH(){cout << flush;}void print(){cout << endl;}template <class Head, class... Tail>void print(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail)) cout << spa;print(forward<Tail>(tail)...);}template<typename T>void print(vector<T> &A){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i != n - 1) cout << ' ';}cout << endl;}template<typename T>void print(vector<vector<T>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void print(pair<T, S> &A){cout << A.first << spa << A.second << endl;}template<typename T, typename S>void print(vector<pair<T, S>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void prisep(vector<T> &A, S sep){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i == n - 1) cout << endl;else cout << sep;}}template<typename T, typename S>void priend(T A, S end){cout << A << end;}template<typename T>void priend(T A){priend(A, spa);}template<class... T>void inp(T&... a){(cin >> ... >> a);}template<typename T>void inp(vector<T> &A){for(auto &a:A) cin >> a;}template<typename T>void inp(vector<vector<T>> &A){for(auto &row:A) inp(row);}template<typename T, typename S>void inp(pair<T, S> &A){inp(A.first, A.second);}template<typename T, typename S>void inp(vector<pair<T, S>> &A){for(auto &row: A) inp(row.first, row.second);}template<typename T>T sum(vector<T> &A){T tot = 0;for(auto a:A) tot += a;return tot;}template<typename T>pair<vector<T>, map<T, int>> compression(vector<T> X){sort(all(X));X.erase(unique(all(X)), X.end());map<T, int> mp;for(int i = 0; i < X.size(); i++) mp[X[i]] = i;return {X, mp};}#line 2 "Library/C++/other/Modint.hpp"template<int MOD>struct Modint{int x;Modint() : x(0){}Modint(int64_t y){if(y >= 0) x = y % MOD;else x = (y % MOD + MOD) % MOD;}Modint &operator+=(const Modint &p){x += p.x;if(x >= MOD) x -= MOD;return *this;}Modint &operator-=(const Modint &p){x -= p.x;if(x < 0) x += MOD;return *this;}Modint &operator*=(const Modint &p){x = int(1LL * x * p.x % MOD);return *this;}Modint &operator/=(const Modint &p){*this *= p.inverse();return *this;}Modint &operator%=(const Modint &p){assert(p.x == 0);return *this;}Modint operator-() const{return Modint(-x);}Modint& operator++() {x++;if (x == MOD) x = 0;return *this;}Modint& operator--() {if (x == 0) x = MOD;x--;return *this;}Modint operator++(int) {Modint result = *this;++*this;return result;}Modint operator--(int) {Modint result = *this;--*this;return result;}friend Modint operator+(const Modint &lhs, const Modint &rhs){return Modint(lhs) += rhs;}friend Modint operator-(const Modint &lhs, const Modint &rhs){return Modint(lhs) -= rhs;}friend Modint operator*(const Modint &lhs, const Modint &rhs){return Modint(lhs) *= rhs;}friend Modint operator/(const Modint &lhs, const Modint &rhs){return Modint(lhs) /= rhs;}friend Modint operator%(const Modint &lhs, const Modint &rhs){assert(rhs.x == 0);return Modint(lhs);}bool operator==(const Modint &p) const{return x == p.x;}bool operator!=(const Modint &p) const{return x != p.x;}bool operator<(const Modint &rhs) {return x < rhs.x;}bool operator<=(const Modint &rhs) {return x <= rhs.x;}bool operator>(const Modint &rhs) {return x > rhs.x;}bool operator>=(const Modint &rhs) {return x >= rhs.x;}Modint inverse() const{int a = x, b = MOD, u = 1, v = 0, t;while(b > 0){t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}return Modint(u);}Modint pow(int64_t k) const{Modint ret(1);Modint y(x);while(k > 0){if(k & 1) ret *= y;y *= y;k >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Modint &p){return os << p.x;}friend istream &operator>>(istream &is, Modint &p){int64_t y;is >> y;p = Modint<MOD>(y);return (is);}static int get_mod(){return MOD;}};struct Arbitrary_Modint{int x;static int MOD;static void set_mod(int mod){MOD = mod;}Arbitrary_Modint() : x(0){}Arbitrary_Modint(int64_t y){if(y >= 0) x = y % MOD;else x = (y % MOD + MOD) % MOD;}Arbitrary_Modint &operator+=(const Arbitrary_Modint &p){x += p.x;if(x >= MOD) x -= MOD;return *this;}Arbitrary_Modint &operator-=(const Arbitrary_Modint &p){x -= p.x;if(x < 0) x += MOD;return *this;}Arbitrary_Modint &operator*=(const Arbitrary_Modint &p){x = int(1LL * x * p.x % MOD);return *this;}Arbitrary_Modint &operator/=(const Arbitrary_Modint &p){*this *= p.inverse();return *this;}Arbitrary_Modint &operator%=(const Arbitrary_Modint &p){assert(p.x == 0);return *this;}Arbitrary_Modint operator-() const{return Arbitrary_Modint(-x);}Arbitrary_Modint& operator++() {x++;if (x == MOD) x = 0;return *this;}Arbitrary_Modint& operator--() {if (x == 0) x = MOD;x--;return *this;}Arbitrary_Modint operator++(int) {Arbitrary_Modint result = *this;++*this;return result;}Arbitrary_Modint operator--(int) {Arbitrary_Modint result = *this;--*this;return result;}friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) += rhs;}friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) -= rhs;}friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) *= rhs;}friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){return Arbitrary_Modint(lhs) /= rhs;}friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs){assert(rhs.x == 0);return Arbitrary_Modint(lhs);}bool operator==(const Arbitrary_Modint &p) const{return x == p.x;}bool operator!=(const Arbitrary_Modint &p) const{return x != p.x;}bool operator<(const Arbitrary_Modint &rhs) {return x < rhs.x;}bool operator<=(const Arbitrary_Modint &rhs) {return x <= rhs.x;}bool operator>(const Arbitrary_Modint &rhs) {return x > rhs.x;}bool operator>=(const Arbitrary_Modint &rhs) {return x >= rhs.x;}Arbitrary_Modint inverse() const{int a = x, b = MOD, u = 1, v = 0, t;while(b > 0){t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}return Arbitrary_Modint(u);}Arbitrary_Modint pow(int64_t k) const{Arbitrary_Modint ret(1);Arbitrary_Modint y(x);while(k > 0){if(k & 1) ret *= y;y *= y;k >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Arbitrary_Modint &p){return os << p.x;}friend istream &operator>>(istream &is, Arbitrary_Modint &p){int64_t y;is >> y;p = Arbitrary_Modint(y);return (is);}static int get_mod(){return MOD;}};int Arbitrary_Modint::MOD = 998244353;using modint9 = Modint<998244353>;using modint1 = Modint<1000000007>;using modint = Arbitrary_Modint;#line 197 "A.cpp"using mint = modint9;#line 2 "Library/C++/data_structure/BIT.hpp"template<typename T>struct BIT{int n;vector<T> tree;BIT(int n): n(n){tree.assign(n + 1, T(0));}BIT(){}T _sum(int i){i++;T res = T(0);while(i > 0){res += tree[i];i -= i & -i;}return res;}T sum(int l, int r){return _sum(r - 1) - _sum(l - 1);}T sum(int r){return _sum(r - 1);}T get(int i){return _sum(i) - _sum(i - 1);}void add(int i, T x){i++;while(i <= n){tree[i] += x;i += i & -i;}}int lower_bound(T x){int pos = 0;int plus = 1;while(plus * 2 <= n) plus *= 2;while(plus > 0){if((pos + plus <= n) && (tree[pos + plus] < x)){x -= tree[pos + plus];pos += plus;}plus >>= 1;}return pos;}};#line 199 "A.cpp"void solve(){INT(n);VEC(int, P, n);fori(i, n) P[i]--;BIT<mint> cnt(n);BIT<mint> tot(n);mint ans = 0;mint add = 1;for(auto p:P){mint cc = cnt.sum(p, n);mint tt = tot.sum(p, n);ans += cc - tt / add;cnt.add(p, 1);tot.add(p, add);add *= 2;}ans *= mint(2).pow(n - 1);print(ans);}int main(){cin.tie(0)->sync_with_stdio(0);// cout << fixed << setprecision(12);int t;t = 1;// cin >> t;while(t--) solve();return 0;}