标签（Label）
网址（Website）
题目（Problem）
题解（Solution）
推一下为什么期望为什么使概率的倒数。
假设只有一个 $1$ ，剩下的全是 $0$ ，我们最后就是要把这个 $1$ 丢到最后面去，选中这个 $1$ 和最后面的 $0$ 的概率是 $\frac{1}{C_{n}^{2}}$ ，令 $p=\frac{1}{C_{n}^{2}}$ 。
由定义式：期望$=$概率$\times$贡献，得：
$$
E=\sum_{i=1}^\infty i\times p\times(1-p)^{i-1}
$$
那么：
$$
(1-p)E=\sum_{i=1}^\infty i\times p\times(1-p)^{i}
$$
$(2)-(1)$ 得：
$$
pE=\sum_{i=1}^\infty p\times(1-p)^{i-1}
$$
即：
$$
E=\sum_{i=1}^\infty (1-p)^{i-1}
$$
则：
$$
(1-p)E=\sum_{i=1}^\infty (1-p)^{i}
$$
$(4)-(5)$ 得：
$$
pE=(1-p)^0=1
$$
则有：
$$
E = \frac{1}{p}
$$
证毕。
剩下的就非常好做了，我们只需要找出所有有效交换的方案数，再除以总的方案数，就是这一次选择有效的概率（可以看出题者题解了解这个做法），容易发现概率是 $\frac{k}{C_{n}^{2}}$ 的形式，在上面每个式子里面都乘上 $k$ ，那么有：
$$
E=\frac{k}{p}
$$
这个就是有一次有效操作期望操作步数，而我们最后就是要让所有的 $1$ 在右边，$0$ 在左边，因此要把每一次算出来的期望步数相加。
时间复杂度 $O(n)$ 。
出题者题解
代码（Code）
100分
#include<bits/stdc++.h> #include<vector> #define For(i,l,r) for(int i=l;i<=r;i++) #define Rof(i,l,r) for(int i=l;i>=r;i--) #define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n' using namespace std; #define P pair<int,int> #define int long long #define x first #define y second #define in(x,l,r) (l<=x && x<=r) inline int rd(){ char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48; while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x; }template<typename G> void write(G x){ if(x<0) putchar('-'),write(-x); else if(x<=9) putchar('0'+x); else write(x/10),putchar('0'+x%10); }constexpr int inf = 0x3f3f3f3f3f3f3f3f; constexpr int N = 1012345; constexpr int mod = 998244353; bool ST;int tid,Tt; inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;} inline void mul(int &x,int y){x=x*y%mod;} int fac[N], inv[N]; inline int ksm(int x,int k=mod-2){ int res=1;while(k){ if(k&1) mul(res,x); mul(x,x), k>>=1; }return res; }inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;} int n,ans; int a[N]; void Solve(){ n=rd();For(i,1,n) a[i]=rd(); int s = 0, l = 0; For(i,1,n) s += a[i]==1; For(i,1,n-s){ if(a[i]==1){ l++; add(ans, C(n,2)*ksm(l*l%mod)%mod); } } write(ans), putchar('\n'); } bool ED; signed main(){ cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n"; freopen("palette.in","r",stdin); freopen("palette.out","w",stdout); tid=rd(),Tt=1;double Tim=clock(); fac[0]=1;For(i,1,N-5) fac[i]=fac[i-1]*i%mod; inv[N-5] = ksm(fac[N-5]); Rof(i,N-6,0) inv[i] = inv[i+1]*(i+1)%mod; while(Tt--) Solve(); return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0; }
