結果
| 問題 | No.2327 Inversion Sum |
| コンテスト | |
| ユーザー |
 HIcoder
|
| 提出日時 | 2023-07-20 16:05:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 71 ms / 2,000 ms |
| コード長 | 6,907 bytes |
| コンパイル時間 | 1,754 ms |
| コンパイル使用メモリ | 114,272 KB |
| 最終ジャッジ日時 | 2025-02-15 15:53:57 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
//AC
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<tuple>
#include<cmath>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD=998244353;
//xのy乗
ll mod_pow(ll x,ll y,ll mod){
ll power=x;
ll ret = 1;
while(y>0){
if(y&1){
ret = ret*power%mod;
}
power = power*power%mod;
y = y>>1;
}
return ret;
}
struct combination{
typedef long long ll;
std::vector<ll> fact,ifact;
combination(ll n): fact(n+1),ifact(n+1){
fact[0]=1;//0!=1通り
for(ll i=1;i<=n;i++) fact[i] = fact[i-1]*i%MOD;
//ifact[n] = fact[n].inv();
// n!の逆元がifact[n]
ifact[n] = mod_pow(fact[n],MOD-2,MOD);// n!を(mod-2)乗した後でmodであまりをとった
for(ll i=n;i>=1;i--) ifact[i-1] = ifact[i]*i%MOD;
}
ll operator()(ll n,ll k){
if(k<0 || k>n) return 0;
// n!/( k!*(n-k)! )
return (fact[n]*ifact[k])%MOD * ifact[n-k]%MOD;
}
};
//転倒数を数えるために用いる
template<class Type> struct binary_indexed_tree{
int N;
vector<Type> bit;
binary_indexed_tree(int n):N(n+1){
bit = vector<Type>(n+1,0);
N=n;
}
void add(int x,Type a){
x++;//1から始めるための補正
//for(int i=x; i<=N; i+=(i&-i)) bit[i] = addition(bit[i],a);
while(x<=N){
//bit[x] = addition(bit[x],a);
bit[x] =bit[x]+a;
x += x&-x;
}
}
Type sum(int x){
x++;//1から始まることに注意
Type ret=0;
//for(int i=x; i>0; i-=(i&-i)) ret = addition(ret,bit[i]);
while(x>0){
ret = ret+bit[x];
x -= x&-x;
}
return ret;
}
//[l,r]の範囲
// rはN-1以下
Type get(int l,int r){
if(r>N) return 0;//配列の外へのアクセス
if(l>r) return 0;//本来は l<=r となるのでおかしい
if(l==0) return sum(r);//[0,r]//ここでoutなわけか
else return (sum(r) - sum(l-1));
}
};
combination comb(2*100000+10);
//転倒数のカウントに用いる
ll calc(vector<int> arg){
ll res=0;
//segment_tree<int,op,e> seg();
const int MAXN=1e5;
binary_indexed_tree<int> bit(MAXN+5);
//順列に出現する順番で見ていく
for(int v:arg){
//vよりも大きい値で インデックスがvよりも小さい数
res+=bit.get(v+1,MAXN+1);
bit.add(v,1);
}
return res;
};
int main(){
int N,M;
cin>>N>>M;
vector<pair<int,int>> PM(M);
vector<int> P(M),K(M);
//vector<int> L(N,1);//L[i]=順列の0~i番目までで,空きがある場所
vector<int> R(N,1);//R[i]=順列のi~N-1番目までで,空きがある場所
for(int i=0;i<M;i++){
cin>>P[i]>>K[i];
P[i]--;K[i]--;
//数字P[i]が数列のK[i]番目にある
PM[i]=make_pair(P[i],K[i]);
}
ll ans=0;
{
ll cnt=0;
//X,Yのどちらも固定されている場合
sort(PM.begin(),PM.end(),
[](const pair<int,int>& lhs,const pair<int,int>& rhs){
return lhs.second<rhs.second;
});
//インデックスが昇順になるようにソート
vector<int> ord;
for(auto [p,k]:PM){//数字のみを取り出す
ord.push_back(p);
}
ll res=calc(ord);
res%=MOD;
//(N-M)!をかける
cnt=res*comb.fact[N-M]%MOD;
ans+=cnt;
ans%=MOD;
}
{
//Xのみ順列の指定位置.Yの指定がない
vector<int> L(N,1);//L[i]=順列の0~i番目までで,空きがある場所
vector<int> usednum;//すでに条件で出現した数字
for(int i=0;i<M;i++){
usednum.push_back(P[i]);//数字
L[K[i]]=0;
}
sort(usednum.begin(),usednum.end());
for(int i=1;i<N;i++){
L[i]=L[i-1]+L[i];
}
for(int i=0;i<M;i++){
int p=P[i],k=K[i];//数字pが順列中にある場所k
int Li=0;//0~k-1までで空きマスの数
if(k-1>=0){
Li=L[k-1];
}
//usednumのうちの数字pより大きいものは何個あるか
//[,usednum.end())
int num = usednum.end() - upper_bound(usednum.begin(),usednum.end(),p);
//p+1~N-1のうち, num個が使われている.
//(Yの選び方) =[p+1,N-1]-num = (N-1)-(p+1)+1 - num
ll cnt=(max(0,N-p-1-num))%MOD;
cnt*=Li%MOD;
cnt%=MOD;
if(N-M-1>=0){
cnt*=comb.fact[N-M-1];
cnt%=MOD;
}else{
cnt=0;
}
ans+=cnt;
ans%=MOD;
}
}
{
//Yのみ順列が固定 Xは固定されない
vector<int> R(N,1);//R[i]=順列のi~N-1番目までで,空きがある場所
vector<int> usednum;
for(int i=0;i<M;i++){
usednum.push_back(P[i]);//すでに条件で使われた数のリスト
R[K[i]]=0;
}
sort(usednum.begin(),usednum.end());
for(int i=N-2;i>=0;i--){
R[i]=R[i]+R[i+1];
}
//Yのみ順列の指定の位置.
for(int i=0;i<M;i++){
int p=P[i],k=K[i];//数字pが順列中にある場所k
int Ri=0;//k+1~N+1までで空きマスの数
if(k+1<N){
Ri=R[k+1];
}
//p未満でusednumに使われている数
int num = upper_bound(usednum.begin(),usednum.end(),p-1)- usednum.begin();
//Yの選び方=[0,p-1] - num = p-num;
ll cnt=max(p-num,0);
cnt*=Ri%MOD;
cnt%=MOD;
if(N-M-1>=0){
cnt*=comb.fact[N-M-1];
cnt%=MOD;
}else{
cnt=0;
}
ans+=cnt;
ans%=MOD;
}
}
{
//X,Yのどちらも指定がない場合.ただし X<Y とする
/*
X,Yの選び方(ただしX<Y)で (n-m)C2
X,Yを入れる場所の選び方で (n-m)C2 ただし, (Yの座標)<(Xの座標)となるようにする
のこりの N-M-2個の数字の順列で(N-M-2)!とおり
*/
ll cnt=comb(N-M,2)*comb(N-M,2)%MOD;
ll fa=0;
if(N-M-2>=0){
fa=comb.fact[N-M-2];
}
cnt=cnt*fa%MOD;
ans+=cnt;
ans%=MOD;
}
cout<<ans<<endl;
}