結果
問題 | No.2250 Split Permutation |
ユーザー |
|
提出日時 | 2023-03-17 22:19:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 3,000 ms |
コード長 | 3,070 bytes |
コンパイル時間 | 760 ms |
コンパイル使用メモリ | 74,796 KB |
最終ジャッジ日時 | 2025-02-11 13:25:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <atcoder/fenwicktree>using namespace std;using namespace atcoder;template <int MOD>struct StaticModint{using mint = StaticModint;public:int val;StaticModint() : val(0) {}StaticModint(long long v){if (std::abs(v) >= mod()){v %= mod();}if (v < 0){v += mod();}val = v;}mint &operator++(){val++;if (val == mod()){val = 0;}return *this;}mint &operator--(){if (val == 0){val = mod();}val--;return *this;}mint &operator+=(const mint &x){val += x.val;if (val >= mod()){val -= mod();}return *this;}mint &operator-=(const mint &x){val -= x.val;if (val < 0){val += mod();}return *this;}mint &operator*=(const mint &x){val = (int)((long long)val * x.val % mod());return *this;}mint &operator/=(const mint &x){*this *= x.inv();return *this;}mint operator-(){return mint() - *this;}mint pow(long long n) const{mint x = 1, r = *this;while (n){if (n & 1){x *= r;}r *= r;n >>= 1;}return x;}mint inv() const{return pow(mod() - 2);}friend mint operator+(const mint &x, const mint &y){return mint(x) += y;}friend mint operator-(const mint &x, const mint &y){return mint(x) -= y;}friend mint operator*(const mint &x, const mint &y){return mint(x) *= y;}friend mint operator/(const mint &x, const mint &y){return mint(x) /= y;}friend bool operator==(const mint &x, const mint &y){return x.val == y.val;}friend bool operator!=(const mint &x, const mint &y){return x.val != y.val;}friend std::ostream &operator<<(std::ostream &os, const mint &x){return os << x.val;}friend std::istream &operator>>(std::istream &is, mint &x){long long v;is >> v;x = mint(v);return is;}private:static constexpr int mod(){return MOD;}};using mint = StaticModint<998244353>;int main(){int n;cin >> n;int p[200005], q[200005];for(int i = 0; i < n; i++){cin >> p[i];p[i]--;q[p[i]] = i;}mint ans = 0;fenwick_tree<mint> bit0(n), bit1(n);for(int i = 0; i < n; i++){ans += bit0.sum(q[i], n) - bit1.sum(q[i], n) * mint(2).pow(q[i]);bit0.add(q[i], mint(2).pow(n - 1));bit1.add(q[i], mint(2).pow(n - 1 - q[i]));}cout << ans << endl;}