赞
踩
题意
给你一个数组,有些位置是-1,代表可以填数,要求填数之后数组为一个1-n的排列,求所有满足条件的填数方案中的逆序数的期望个数。
做法
记一共n个数,其中m个未知,因此可能的排列结果有m!种
我们分四种情况计数逆序对
1.已知和已知:简单的逆序对计数,对于每种排列贡献相同,所以要乘m!,做法可以用归并排序或者树状数组
2.未知和未知:考虑任意一对数会在一半的排列里成为逆序对,因此总共有 m ! ∗ ( m − 1 ) ∗ m 4 \frac{m!*(m-1)*m}{4} 4m!∗(m−1)∗m
3.已知和未知:遍历每个已知数,考虑他前面的空位,以及未知数里有几个比他大的,不妨记为k个空位,s个比他大的数,那么考虑每个数可以放在某个空位,剩下数任意排列的方案数是(m-1)!,因此这个已知数和比他大的数构成逆序对贡献为(m-1)!ks
4.未知和已知:遍历每个已知数,考虑他后面的空位,以及未知数里有几个比他小的,不妨记为k个空位,s个比他小的数,那么考虑每个数可以放在某个空位,剩下数任意排列的方案数是(m-1)!,因此这个已知数和比他小的数构成逆序对贡献为(m-1)!ks
对以上逆序对数求和,就得到了所有情况下的逆序对总数;一共有m!种情况,期望就算出来了。过程理解起来简单,但是实现起来有些小细节,需要注意一下。
代码
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 2e5+5; const int Mod=998244353; int c[maxn]; int lowbit(int i) { return i&(-i); } void add(int i)//i从1开始 { while(i<maxn) { c[i]++; i+=lowbit(i); } return ; } int sum(int i)//求和l,r.sum(r)-sum(l-1) { int sum=0; while(i>0) { sum+=c[i]; i-=lowbit(i); } return sum; } ll pow_(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%Mod; a=a*a%Mod; b>>=1; } return ans; } ll inv_(ll x) { return pow_(x,Mod-2); } int a[maxn],pre[maxn],vis[maxn]; ll Fac[maxn]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); Fac[0]=1; for(int i=1;i<=n;i++) Fac[i]=Fac[i-1]*i%Mod; ll all=0; for(int i=1;i<=n;i++) { if(a[i]!=-1) { all++; vis[a[i]]++; } } int vv=0; for(int i=n;i>=1;i--) { pre[i]=vv; if(vis[i]) vv++; } ll ans=0,cnt=0; for(int i=1;i<=n;i++) { if(a[i]==-1) cnt++; else { ans=(ans+Fac[n-all]*(sum(maxn-1)-sum(a[i]))%Mod+Mod)%Mod; add(a[i]); ans=(ans+1LL*(n-all-cnt)*(a[i]-all+pre[a[i]])%Mod*Fac[n-all-1]%Mod)%Mod; ans=(ans+1LL*cnt*(n-a[i]-pre[a[i]])%Mod*Fac[n-all-1]%Mod)%Mod; } } ans=(ans+Fac[cnt]*cnt%Mod*(cnt-1)%Mod*inv_((ll)4)%Mod)%Mod; ans=ans*inv_(Fac[cnt])%Mod; printf("%lld\n",ans); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。