結果
問題 | No.2250 Split Permutation |
ユーザー |
|
提出日時 | 2023-03-17 23:21:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 450 ms / 3,000 ms |
コード長 | 1,911 bytes |
コンパイル時間 | 3,899 ms |
コンパイル使用メモリ | 188,188 KB |
最終ジャッジ日時 | 2025-02-11 14:31:01 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <functional>#include <cmath>#include <iomanip>#include <stack>#include <queue>#include <numeric>#include <map>#include <unordered_map>#include <set>#include <fstream>#include <chrono>#include <random>#include <bitset>#include <atcoder/all>#define rep(i,n) for(int i=0;i<(n);i++)#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) ((int)(x).size())#define pb push_backusing ll = long long;using namespace std;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}const ll mod = 998244353;vector<ll> p2,p2i;ll mpow(ll a, ll x){ll res = 1;while(x > 0){if(x & 1) res = (res * a) % mod;a = (a * a) % mod;x >>= 1;}return res;}ll inv(ll x){ll res = 1, k = mod - 2;while(k){if(k&1) res = (res * x) % mod;x = (x * x) % mod;k >>= 1;}return res;}ll op1(ll a,ll b){return (a+b)%mod;}ll e1(){return 0LL;}ll op(ll a,ll b){return (a+b)%mod;}ll e(){return 0LL;}ll mapping(ll f, ll x){return x * p2i[f] % mod;}ll composition(ll f, ll g){return f+g;}ll id(){return 0LL;}int main(){p2.resize(300000);rep(i,300000) p2[i] = mpow(2,i);p2i.resize(300000);rep(i,300000) p2i[i] = inv(p2[i]);ll N; cin >> N;vector<ll> A(N);rep(i,N) cin >> A[i];rep(i,N) A[i]--;atcoder::segtree<ll,op1,e1> seg1(N);atcoder::lazy_segtree<ll,op,e,ll,mapping,composition,id> seg(N);ll ans = 0;rep(i,N){seg.apply(0,N,1);ans += (seg1.prod(A[i]+1,N)-seg.prod(A[i]+1,N)+mod)%mod * p2[N-1] % mod;seg.set(A[i],1);seg1.set(A[i],1);}cout << ans%mod << '\n';return 0;}