結果
問題 | No.2250 Split Permutation |
ユーザー |
|
提出日時 | 2023-03-17 22:48:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 287 ms / 3,000 ms |
コード長 | 2,696 bytes |
コンパイル時間 | 2,355 ms |
コンパイル使用メモリ | 196,096 KB |
最終ジャッジ日時 | 2025-02-11 13:54:34 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define INF (int)1e18#define f first#define s secondmt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());const int N = 2e5 + 69;const int mod = 998244353;int a[N], n;int seg1[4*N];int seg[4*N];int pow2[2*N];int power(int x, int y){if (y==0) return 1;int v = power(x, y/2); v *= v; v %= mod;if (y&1) return v * x % mod;else return v;}void Update(int l, int r, int pos, int qp, int val){seg[pos] += val; seg[pos] %= mod;if (l==r) return;int mid = (l+r)/2;if (qp <= mid) Update(l, mid, pos*2, qp, val);else Update(mid + 1, r, pos*2 + 1, qp, val);}void Update1(int l, int r, int pos, int qp, int val){seg1[pos] += val;if (l==r) return;int mid = (l+r)/2;if (qp <= mid) Update1(l, mid, pos*2, qp, val);else Update1(mid + 1, r, pos*2 + 1, qp, val);}int Query(int l, int r, int pos, int ql, int qr){if (l>=ql && r<=qr) return seg[pos];else if (l>qr || r<ql) return 0;int mid = (l+r)/2;return (Query(l, mid, pos*2, ql, qr) + Query(mid + 1, r, pos*2 + 1, ql, qr))%mod;}int Query1(int l, int r, int pos, int ql, int qr){if (l>=ql && r<=qr) return seg1[pos];else if (l>qr || r<ql) return 0;int mid = (l+r)/2;return Query1(l, mid, pos*2, ql, qr) + Query1(mid + 1, r, pos*2 + 1, ql, qr);}void Solve(){cin>>n;pow2[0] = 1;for (int i=1; i<=2*n; i++)pow2[i] = pow2[i-1] * 2 % mod;int ans = 0;for (int i=1; i<=n; i++){cin>>a[i];// for (int j=1; j<=n; j++){// cout<<Query1(1, n, 1, j, j)<<" ";// }// cout<<"\n";int v1 = Query1(1, n, 1, a[i], n);int v2 = Query(1, n, 1, a[i], n);ans += v1 * pow2[n-1] % mod;ans -= v2 * power(pow2[i], mod - 2) % mod;// cout<<v1<<" "<<v2<<"\n";Update1(1, n, 1, a[i] , 1);int val = pow2[n + i - 1];Update(1, n, 1, a[i], val);ans %= mod;if (ans < 0) ans += mod;}cout<<ans<<"\n";}int32_t main(){auto begin = std::chrono::high_resolution_clock::now();ios_base::sync_with_stdio(0);cin.tie(0);int t = 1;//cin >> t;for(int i = 1; i <= t; i++){//cout << "Case #" << i << ": ";Solve();}auto end = std::chrono::high_resolution_clock::now();auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";return 0;}