結果

問題 No.2327 Inversion Sum
ユーザー 0214sh70214sh7
提出日時 2023-05-28 15:41:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,413 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 206,768 KB
最終ジャッジ日時 2025-02-13 13:45:28
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 false
class compress{
/*
Copyright (c) 2021 0214sh7
https://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 0214sh7
https://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 0214sh7
https://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);
}
//REP(i,N){cout << Z[i] << " ";}cout << endl;
//REP(i,E.size()){cout << E[i] << " ";}cout << endl;
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]);}
//REP(i,X.size()){cout << X[i] << " ";}cout << endl;
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;
sum += N-M-u;
}
}
/*REP(i,N){
cout << W[i] << " ";
}
cout << Endl;*/
ll num = 0;
REP(i,N){
if(Z[i]!=-1){
/*auto it = upper_bound(ALL(E),Z[i]);it--;
ll u = distance(E.begin(),it);
Ans = (Ans+((N-M-now)*u)%MOD)%MOD;
Ans = (Ans+(now*(E.size()-1-u))%MOD)%MOD;
cout << now MM u MM (N-M-now) MM (E.size()-1-u) << endl;*/
sum -= N-M-W[Z[i]];
sum += W[Z[i]];
}else{
num += sum;
}
}
//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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0