codeforces1027D Number Of Permutations（容斥）

曾经终败给现在 2024-04-17 05:49 60阅读 0赞

## 题意：n个二维数对(ai,bi)，求将n个数对排列之后，ai,bi都不是单调不减的。这样的排列有多少个。 ##

## 分析：简单容斥。答案为总的排列数-（ai单调不减或者bi单调不减的排列数）+（ai,bi都单调不减的排列数）。ai单调不减或者bi单调不减的方案分别排序记录相邻位置相同树的个数就行。考虑如何计算ai、bi都单调不减的排列数。我们就在按a排序的基础上在按b排序，注意要判断整个序列是否满足b不降（因为这个wa了），如果满足，则去每一段相同的a中找b相同连续段。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    const ll mod = 998244353;
    ll n,f[N];
    struct nd {
        int l,r;
    }p[N];
    bool cmp(nd a,nd b) {
        return a.r<b.r;
    }
    
    bool cmp2(nd a,nd b) {
        if(a.l==b.l) return a.r<b.r;
        return a.l<b.l;
    }
    
    int main() {
        f[1]=1;
        for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>p[i].l>>p[i].r;
        sort(p+1,p+1+n,cmp);
        ll s1=1,s2=1,cnt=1;
        for(int i=2;i<=n;i++) {
            if(p[i].r==p[i-1].r) cnt++;
            else (s1*=f[cnt])%=mod,cnt=1;
        }
        (s1*=f[cnt])%=mod;
        cnt=1;
        sort(p+1,p+1+n,cmp2);
        for(int i=2;i<=n;i++) {
            if(p[i].l==p[i-1].l) cnt++;
            else (s2*=f[cnt])%=mod,cnt=1;
        }
        (s2*=f[cnt])%=mod;
        cnt=1;
        int fg=0;
        for(int i=2;i<=n;i++)
            if(p[i].r<p[i-1].r) fg=1;
        if(fg) cout<<(f[n]-s1-s2+2*mod)%mod<<endl;
        else {
            ll s3=1;
            for(int i=2;i<=n;i++) {
                if((p[i].l==p[i-1].l)&&(p[i].r==p[i-1].r)) cnt++;
                else (s3*=f[cnt])%=mod,cnt=1;
            }
            (s3*=f[cnt])%=mod;
            cout<<(f[n]-s1+mod-s2+mod+s3)%mod<<endl;
        }
        return 0;
    }