牛客网212D禁书目录Index-题解

【题目地址】

题意简述

给你一些二元组$(x,y)$，对于这些二元组的一个排列，如果一个二元组$i$的左边有$x_j\ge x_i$，那么这个二元组就会消失。

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

---

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

正解

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

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

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

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

$$val=n!\times (1-\prod (1-k_i))$$

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

答案就为$\sum val$

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

代码简陋的QAQ：

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

#include<vector> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using 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<a.A;} }Bk[M]; void init(){ Inv[1]=1; for(int i=2;i<=n+1;i++)Inv[i]=(Mod-Mod/i)*Inv[Mod%i]%Mod; fac=1;for(int i=2;i<=n;i++)fac=(fac*i)%Mod; } int sze[M],tct; struct node{ int A,t; node(){} node(int a,int b):A(a),t(b){} bool operator <(const node &a)const{return A<a.A;} }; vector <node> Type[M]; vector <ll> 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<sz;j++){ if(last!=Type[i][j].A){ if(last!=-1){rec[i].push_back((Mod+1-(cnt*Inv[Type[i][j-1].t]%Mod))%Mod);} last=Type[i][j].A; cnt=1;p=j; }else{++cnt;} } } ll ans=0; for(int i=1;i<=tot;i++){ ll now=1; for(int j=0,sz=rec[i].size();j<sz;j++)now=(now*rec[i][j])%Mod; now=(Mod+1-now)%Mod; ans=(ans+fac*now%Mod)%Mod; } printf("%lld\n",ans%Mod); return 0; }