結果
問題 | No.2250 Split Permutation |
ユーザー |
![]() |
提出日時 | 2023-03-18 00:27:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 122 ms / 3,000 ms |
コード長 | 1,491 bytes |
コンパイル時間 | 957 ms |
コンパイル使用メモリ | 77,336 KB |
最終ジャッジ日時 | 2025-02-11 14:38:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>#include <atcoder/modint>namespace nono {template<typename T>class FenwickTree {public:FenwickTree(const int size) : size_(size + 1), data_(size + 1) {}FenwickTree(const std::vector<T> &vec) : size_(vec.size() + 1), data_(vec.size() + 1) {for (int i = 0; i < size_; ++i) {add(i, vec[i]);}}void add(int i, const T delta) {for (i++; i < size_; i += i & -i) {data_[i] += delta;}}T get_range(const int l, const int r) {return get_sum(r) - get_sum(l);}T operator[](const int i) {return get_range(i, i + 1);}private:const int size_;std::vector<T> data_;T get_sum(int i) {T sum = 0;for (; i > 0; i -= i & -i) {sum += data_[i];}return sum;}};} // namespace nonousing mint = atcoder::modint998244353;int main() {int n;std::cin >> n;std::vector<int> p(n);for (int i = 0; i < n; i++) std::cin >> p[i];nono::FenwickTree<int> count(n);nono::FenwickTree<mint> fen(n);mint ans = 0;mint up = 1;mint down = mint(2).pow(n - 1);for (int i = 0; i < n; i++) {p[i]--;ans += count.get_range(p[i], n) * mint(2).pow(n - 1) - fen.get_range(p[i], n) * down;count.add(p[i], 1);fen.add(p[i], up);up *= 2;down /= 2;}std::cout << ans.val() << '\n';}