結果
問題 | No.2327 Inversion Sum |
ユーザー |
|
提出日時 | 2023-05-09 21:13:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 6,595 bytes |
コンパイル時間 | 2,246 ms |
コンパイル使用メモリ | 201,840 KB |
最終ジャッジ日時 | 2025-02-12 21:05:24 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <long long Modulus>struct ModInt{long long val;constexpr ModInt(const long long &_val = 0) noexcept : val(_val) {normalize();}void normalize(){val = (val % Modulus + Modulus) % Modulus;}inline ModInt& operator+=(const ModInt& rhs) noexcept {if(val += rhs.val, val >= Modulus) val -= Modulus;return *this;}inline ModInt& operator-=(const ModInt& rhs) noexcept {if(val -= rhs.val, val < 0) val += Modulus;return *this;}inline ModInt& operator*=(const ModInt& rhs) noexcept {val = val * rhs.val % Modulus;return *this;}inline ModInt& operator/=(const ModInt& rhs) noexcept {val = val * inv(rhs.val).val % Modulus;return *this;}inline ModInt& operator++() noexcept {if(++val >= Modulus) val -= Modulus;return *this;}inline ModInt operator++(int) noexcept {ModInt t = val;if(++val >= Modulus) val -= Modulus;return t;}inline ModInt& operator--() noexcept {if(--val < 0) val += Modulus;return *this;}inline ModInt operator--(int) noexcept {ModInt t = val;if(--val < 0) val += Modulus;return t;}inline ModInt operator-() const noexcept { return (Modulus - val) % Modulus; }inline ModInt inv(void) const { return inv(val); }ModInt inv(const long long& n) const {long long a = n, b = Modulus, u = 1, v = 0;while(b){long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= Modulus;if(u < 0) u += Modulus;return u;}friend inline ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }friend inline ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }friend inline ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }friend inline ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }friend inline bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.val == rhs.val; }friend inline bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.val != rhs.val; }friend inline istream& operator>>(istream& is, ModInt& x) noexcept {is >> x.val;x.normalize();return is;}friend inline ostream& operator<<(ostream& os, const ModInt& x) noexcept { return os << x.val; }};struct Combination{vector<long long> memo, memoinv, inv;const long long mod;Combination(const int &N, const long long &m) : memo(N + 1), memoinv(N + 1), inv(N + 1), mod(m){memo[0] = memo[1] = 1;memoinv[0] = memoinv[1] = 1;inv[1] = 1;for(int i = 2; i <= N; ++i){memo[i] = memo[i - 1] * i % mod;inv[i] = mod - inv[mod % i] * (m / i) % mod;memoinv[i] = memoinv[i - 1] * inv[i] % mod;}}inline long long fact(const long long &n) const {return memo[n];}inline long long factinv(const long long &n) const {return memoinv[n];}inline long long ncr(const long long &n, const long long &r) const {if(n < r || r < 0) return 0;return (memo[n] * memoinv[r] % mod) * memoinv[n - r] % mod;}inline long long npr(const long long &n, const long long &r) const {if(n < r || r < 0) return 0;return (memo[n] % mod) * memoinv[n - r] % mod;}inline long long nhr(const long long &n, const long long &r) const {if(n == 0 && r == 0) return 1;return ncr(n + r - 1, r);}};template <typename T>struct BinaryIndexedTree{int N;vector<T> BIT;BinaryIndexedTree(const int &N): N(N), BIT(N + 1, 0){}T get(int i){return sum(i + 1) - sum(i);}void add(int i, T x){i++;while(i <= N){BIT[i] += x;i += i & -i;}}T sum(int i) const {T ans = 0;while(i > 0){ans += BIT[i];i -= i & -i;}return ans;}T sum(int L, int R) const {return sum(R) - sum(L);}int lower_bound(T x) const {if(x <= 0){return 0;}else{int v = 0, r = 1;while(r < N) r = r << 1;for(int len = r; len > 0; len = len >> 1){if(v + len < N && BIT[v + len] < x){x -= BIT[v + len];v += len;}}return v;}}int upper_bound(T x) const {if(x < 0){return 0;}else{int v = 0, r = 1;while(r <= N) r = r << 1;for(int len = r; len > 0; len = len >> 1){if(v + len <= N && BIT[v + len] <= x){x -= BIT[v + len];v += len;}}return v;}}};const long long MOD = 998244353;using mint = ModInt<998244353>;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m; cin >> n >> m;vector<int> c(n, -1), check(n, 1);for(int i = 0; i < m; i++){int p, k; cin >> p >> k;p--, k--;c[k] = p;check[p] = 0;}vector<int> sum_c(n + 1), sum_check(n + 1);for(int i = 0; i < n; i++) sum_c[i + 1] = sum_c[i] + (c[i] != -1);for(int i = 0; i < n; i++) sum_check[i + 1] = sum_check[i] + (check[i]);BinaryIndexedTree<mint> BIT(n);Combination comb(n, MOD);mint ans = 0;mint cntc = 0, cntnc = 0;for(int i = 0; i < n; i++){if(check[i]){cntnc += sum_check[n] - sum_check[i + 1];}}for(int i = 0; i < n; i++){if(c[i] == -1){mint plus = comb.fact(n - m - 2);plus *= i - sum_c[i];plus *= cntnc;ans += plus;ans += cntc * comb.fact(n - m - 1);}else{mint plus = sum_check[n] - sum_check[c[i]];plus *= comb.fact(n - m - 1);plus *= i - sum_c[i];ans += plus;ans += BIT.sum(c[i] + 1, n) * comb.fact(n - m);cntc += sum_check[c[i]];BIT.add(c[i], 1);}}cout << ans << endl;}