【】

• 题意简述

给你一些二元组$(x,y)$，对于这些二元组的一个排列，如果一个二元组$i$的左边有xj≥xix_j\geq x_ixj​≥xi​，那么这个二元组就会消失。

每种排列的贡献值为其中$y$的种类数，然后询问你所有排列的总贡献。

---

暴力枚举排列，然后计算贡献相加，复杂度为$O(n\times n!)$

• 正解

我们这里考虑对$y$进行离散化，然后对二元组按照$x$排序，记录下每一个二元组$x$大于等于它的个数。

那么对于一种二元组会有贡献的话，我们可以计算出它的贡献的概率，概率就为和它一样的二元组个数除以大于等于它的二元组的个数。（因为大于它的要全部排在至少一种这种二元组后面）

那么由于总的方案数就为$n!$，所以得知概率后我们就可以知道它有多少种做出贡献的方案。

对于每一种，我们令kik_iki​为它做出贡献的概率，那由于一种$y$可能有多种$x$，所以我们要反向计算概率贡献，计算式如下：

val=n!×(1−∏(1−ki))val=n!\times (1-\prod (1-k_i))val=n!×(1−∏(1−ki​))

其中ki=cnttotk_i=\frac{cnt}{tot}ki​=totcnt​，$cnt$为同种二元组的个数，$tot$为大于等于这个二元组的个数。

答案就为$\sum val$

用概率或者期望来算方案数的题目，方法比较巧妙，是在知道总方案数的时候的一种较为好的计算方式。

代码简陋的QAQ：

最后线性处理一下阶乘和逆元即可计算取模意义下的答案。

#include
    
     #include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;const int M=5e5+10,Inf=1e9;const ll Mod=998244353ll;int ls[M],maxv[M],minv[M],tot,n;ll Inv[M],fac;struct book{
    	int A,B;	void in(){
    scanf("%d%d",&A,&B);ls[++tot]=B;}	book(){
    }	book(int a,int b):A(a),B(b){
    }	bool operator <(const book &a)const{
    return A
        
          Type[M];vector 
         
           rec[M];int main(){ scanf("%d",&n); init(); for(int i=1;i<=n;i++)Bk[i].in(); sort(ls+1,ls+tot+1); tot=unique(ls+1,ls+tot+1)-ls-1; sort(Bk+1,Bk+n+1); int last=-1,tw=0; for(int i=1;i<=n;i++){ int pos=lower_bound(ls+1,ls+tot+1,Bk[i].B)-ls; if(last!=Bk[i].A)last=Bk[i].A,tw=n-i+1; Type[pos].push_back(node(Bk[i].A,tw)); } for(int i=tot;i>=1;i--)sort(Type[i].begin(),Type[i].end()); for(int i=1;i<=tot;i++){ int last=-1,cnt=0,p=0;Type[i].push_back(node(-1,0)); for(int j=0,sz=Type[i].size();j