結果
問題 | No.2327 Inversion Sum |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:57:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 3,959 bytes |
コンパイル時間 | 2,360 ms |
コンパイル使用メモリ | 206,792 KB |
最終ジャッジ日時 | 2025-02-13 14:44:52 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll,ll> PP;//#define MOD 1000000007#define MOD 998244353#define INF 2305843009213693951//#define INF 810114514#define PI 3.141592653589#define setdouble setprecision#define REP(i,n) for(ll i=0;i<(n);++i)#define OREP(i,n) for(ll i=1;i<=(n);++i)#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)#define ALL(v) (v).begin(), (v).end()#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)#define MM <<" "<<#define Endl endl#define debug true#define debug2 falseclass compress{/*Copyright (c) 2021 0214sh7https://github.com/0214sh7/library/*/private:std::vector<int> E;public:void init(std::vector<long long> A){E.clear();sort(A.begin(),A.end());for(int i=0;i<A.size();i++){if(i==0 || A[i]!=A[i-1]){E.push_back(A[i]);}}}compress(std::vector<long long> A){init(A);}int size(){return (int)E.size();}int value(int x){if(0<=x && x<(int)E.size()){return E[x];}else{return 0;}}int index(int X){return (upper_bound(E.begin(),E.end(),X))-E.begin()-1;}};class Fenwick_tree{/*Copyright (c) 2021 0214sh7https://github.com/0214sh7/library/*/private:std::vector<long long> BIT;public:void add(int a,long long w){for(int x=a;x<BIT.size();x|=(x+1)){BIT[x]+=w;}}void init(int n){BIT.clear();for(int i=0;i<n;i++){BIT.push_back(0);}}Fenwick_tree(int n){init(n);}long long sum(int a){long long r=0;for(int x=a-1;x>=0;x=(x&(x+1))-1){r+=BIT[x];}return r;}long long inversion(std::vector<long long> V){long long r=0;init(V.size());for(int i=0;i<V.size();i++){add(V[i],1);r+=i-sum(V[i]);}return r;}};long long inverse(long long b,long long mod){/*Copyright (c) 2021 0214sh7https://github.com/0214sh7/library/*/long long r=1,e=mod-2;while(e){if(e&1){r=(r*b)%mod;}b=(b*b)%mod;e >>=1;}return r;}int main(void){//cin.tie(nullptr);//ios::sync_with_stdio(false);ll N,M;cin >> N >> M;vector<ll> P(M),K(M);REP(i,M){cin >> P[i] >> K[i];P[i]--;K[i]--;}vector<ll> Y(N,1),Z(N,-1);REP(i,M){Y[P[i]]=0;Z[K[i]]=P[i];}vector<ll> E = {-INF};REP(i,N){if(Y[i]==1)E.push_back(i);}vector<ll> X;REP(i,N){if(Z[i]!=-1)X.push_back(Z[i]);}compress zaatsu(X);REP(i,X.size()){X[i] = zaatsu.index(X[i]);}Fenwick_tree BIT(N);ll Ans = BIT.inversion(X)%MOD;REP(i,N-M){Ans = (Ans*(i+1))%MOD;}//cout << Ans << endl;vector<ll> W(N,0);ll sum = 0;REP(i,N){if(Z[i]!=-1){auto it = upper_bound(ALL(E),Z[i]);it--;ll u = distance(E.begin(),it);W[Z[i]] = u%MOD;sum = (sum+N-M-u)%MOD;}}ll num = 0;REP(i,N){if(Z[i]!=-1){sum = (sum+MOD-(N-M-W[Z[i]]))%MOD;sum = (sum+W[Z[i]])%MOD;}else{num = (num+sum)%MOD;}}//num = (num*(MOD+1)/2)%MOD;num = (num*inverse(N-M,MOD))%MOD;REP(i,N-M){num = (num*(i+1))%MOD;}Ans = (Ans+num)%MOD;//cout << num << endl;//cout << Ans << endl;ll n = N-M;n = (n*(n-1)/2)%MOD;n = (n*(MOD+1)/2)%MOD;REP(i,N-M){n = (n*(i+1))%MOD;}//cout << n << endl;Ans = (Ans+n)%MOD;cout << Ans << endl;return 0;}