結果
問題 | No.2327 Inversion Sum |
ユーザー |
![]() |
提出日時 | 2024-12-06 13:39:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,516 bytes |
コンパイル時間 | 2,108 ms |
コンパイル使用メモリ | 204,972 KB |
最終ジャッジ日時 | 2025-02-26 11:13:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } #include <atcoder/fenwicktree> #include <atcoder/modint> using mint = atcoder::modint998244353; mint fact[200005], inv[200005]; void init() { fact[0] = 1; for (int i = 1; i <= 200000; i++) fact[i] = fact[i - 1] * i; inv[200000] = fact[200000].inv(); for (int i = 199999; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1); } int main() { fast_io(); init(); int n, m; cin >> n >> m; vector<int> a(n, -1); vector<bool> vis(n); for (int i = 0; i < m; i++) { int p, k; cin >> p >> k; p--, k--; a[k] = p; vis[p] = true; } vector<int> unused; for (int i = 0; i < n; i++) { if (!vis[i]) { unused.push_back(i); } } int unused_sz = unused.size(); mint ans = mint(unused_sz) * (unused_sz - 1) / 4 * fact[unused_sz]; { atcoder::fenwick_tree<mint> fw(n); mint inv = 0; for (int i = 0; i < n; i++) { if (a[i] == -1) { continue; } inv += fw.sum(a[i] + 1, n); fw.add(a[i], 1); } ans += inv * fact[unused_sz]; } if (unused_sz == 0) { cout << ans.val() << endl; return 0; } int cnt = 0; for (int i = 0; i < n; i++) { if (a[i] == -1) { cnt++; } else { auto it = lower_bound(unused.begin(), unused.end(), a[i]); int greater = unused.end() - it; int smaller = unused_sz - greater; ans += mint(greater) * fact[unused_sz - 1] * cnt; ans += mint(smaller) * fact[unused_sz - 1] * (unused_sz - cnt); } } cout << ans.val() << endl; }