CF1753C. Wish I Knew How to Sort题解

发表于 2022-10-26 分类于题解

题意：有一个 01 序列，每次可以选择两个元素，如果为逆序则交换，否则不变，无论是否交换都算一次操作。问排好序的期望操作次数。

容易想到使用 DP 计算，但状态并不是很好想。首先状态必须有单向性，必须有严格的 DP 顺序，于是我们可以想到用逆序对数来记录状态。然而，思考会发现并不可行。不仅是复杂度无法接受，仅用逆序对也无法完整地表示状态。实际上，我们可以用“未归位的数字个数”来作为状态。具体地，假设当前序列为 $\texttt{01101011}$ ，该序列一共有三个 0，所以前三位应该都是 0，而实际上有两个 1，就定义此时的“未归位的数字个数”为 $2$ 。这个状态的单向性显然，完整性也容易证明，因为只有“归位”的交换是有意义的，如果没有达到“归位”的效果，无论是否交换都是没有意义的。

做法 1

我们定义 $f[i]$ 表示有 $i$ 个“未归位的数字”时，要想排好序的期望步数。则我们可以考虑期望多少次操作之后能减少一个“未归位的数字”。一次操作“能减少”的方案数显然为左边 1 的个数乘右边 0 的个数，即 $i^2$ ，所以“能减少”的概率 $p_1=\frac{i^2}{n(n-1)/2}=\frac{2i^2}{n(n-1)}$ ，反之“不能减少”的概率即为 $p_2=1-p_1=\frac{n(n-1)-2i^2}{n(n-1)}$ 。于是， $f[i]=\sum\limits_{j=0}^{\infty}{p_2}^j\cdot p_1\cdot(f[i-1]+j+1)$ ，其中 $j$ 表示“失误”了多少次。我们考虑如何计算这个无穷级数：

\begin{aligned} f[i]&=\sum\limits_{j=0}^{\infty}{p_2}^j\cdot p_1\cdot(f[i-1]+j+1)\\ &=p_1\sum\limits_{j=0}^{\infty}{p_2}^j\cdot(f[i-1]+j+1)\\ &=p_1\left(\sum\limits_{j=0}^{\infty}{p_2}^j\cdot(f[i-1]+1)+\sum\limits_{j=0}^{\infty}{p_2}^j\cdot j\right) \end{aligned}

我们令 $x=f[i-1]+1$ ，则第一项简化为 $\sum\limits_{j=0}^{\infty}{p_2}^j\cdot x=x\sum\limits_{j=0}^{\infty}{p_2}^j$ 。设 $S=\sum\limits_{j=0}^{\infty}{p_2}^j$ ，则 $p_2S=\sum\limits_{j=1}^{\infty} p_2^j$ ，两式相减得 $(1-p_2)S={p_2}^0=1$ ，即 $S=\frac{1}{1-p_2}$ 。对于第二项同理，令 $S'=\sum\limits_{j=0}^{\infty}{p_2}^j\cdot j$ ，则 $p_2S'=\sum\limits_{j=1}^{\infty}{p_2}^j(j-1)$ ，两式相减得 $(1-p_2)S'=\sum\limits_{j=1}^{\infty}{p_2}^j=S=\frac{1}{1-p_2}$ ，即 $S'=\frac{1}{(1-p_2)^2}$ 。于是：

f[i]=p_1\left(\frac{f[i-1]+1}{1-p_2}+\frac{1}{(1-p_2)^2}\right)

此即为 DP 方程。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int ksm(int a,int b,int res=1) {
    for(;b;a=a*a%mod,b>>=1)
        if(b&1) res=res*a%mod;
    return res;
}
int inv(int x) {return ksm(x,mod-2);}
int a[200010],f[200010];
void Solve() {
    int n,cnt0=0,cnt1=0;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(a[i]==0) cnt0++;
    }
    for(int i=1;i<=cnt0;i++)
        if(a[i]==1) cnt1++;
    f[0]=0;
    int invall=inv(n*(n-1)%mod);
    for(int i=1;i<=cnt1;i++) {
        int p1=2*i*i%mod*invall%mod;
        int p2=(n*(n-1)%mod-2*i*i%mod+mod)%mod*invall%mod;
        f[i]=p1*(p2*inv((1-p2+mod)%mod*((1-p2+mod)%mod)%mod)%mod+(f[i-1]+1)*inv((1-p2+mod)%mod)%mod)%mod;
    }
    cout<<f[cnt1]<<endl;
}
signed main() {
    int T=1;
    cin>>T;
    while(T--) Solve();
    return 0;
}

做法 2

上面的做法显然过于麻烦了，我们考虑简单一点的转移方式。有一个经典的套路，就是用“从自身转移到自身”的方式来解决无穷级数的问题。在此题中，我们只考虑第一次操作。如果第一次操作恰好选中了该选的数，则为 $f[i-1]+1$ ，概率为 $\frac{2i^2}{n(n-1)}$ ；如果没有选中该选的数，则情况不变，而额外增加了一步，为 $f[i]+1$ ，概率为 $\frac{n(n-1)-2i^2}{n(n-1)}$ 。你可能会有疑问，我们还没有算出 $f[i]$ 来，怎么能转移呢？事实上，如果我们列出了转移方程： $f[i]=\frac{2i^2}{n(n-1)}(f[i-1]+1)+\frac{n(n-1)-2i^2}{n(n-1)}(f[i]+1)$ ，则会发现这转化为了一个简单的解方程问题，直接解出 $f[i]$ 即可：

\begin{aligned} f[i]=&\frac{2i^2}{n(n-1)}\cdot f[i-1]+\frac{n(n-1)-2i^2}{n(n-1)}\cdot f[i]+1\\ \left(1-\frac{n(n-1)-2i^2}{n(n-1)}\right)f[i]=&\frac{2i^2}{n(n-1)}\cdot f[i-1]+1\\ \frac{2i^2}{n(n-1)}\cdot f[i]=&\frac{2i^2}{n(n-1)}\cdot f[i-1]+1\\ f[i]=&f[i-1]+\frac{n(n-1)}{2i^2}\\ \end{aligned}

在此方法下，最终的转移方程如此的简单，只是一个前缀和的形式。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int ksm(int a,int b,int res=1) {
    for(;b;a=a*a%mod,b>>=1)
        if(b&1) res=res*a%mod;
    return res;
}
int inv(int x) {return ksm(x,mod-2);}
int a[200010],f[200010];
void Solve() {
    int n,cnt0=0,cnt1=0;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(a[i]==0) cnt0++;
    }
    for(int i=1;i<=cnt0;i++)
        if(a[i]==1) cnt1++;
    f[0]=0;
    int all=n*(n-1)%mod;
    for(int i=1;i<=cnt1;i++)
        f[i]=(f[i-1]+all*inv(2*i*i%mod)%mod)%mod;
    cout<<f[cnt1]<<endl;
}
signed main() {
    int T=1;
    cin>>T;
    while(T--) Solve();
    return 0;
}

容易发现，该前缀和出去分子后与 $n$ 完全无关，故可以在循环外预处理前缀和，进一步优化实现。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int ksm(int a,int b,int res=1) {
    for(;b;a=a*a%mod,b>>=1)
        if(b&1) res=res*a%mod;
    return res;
}
int inv(int x) {return ksm(x,mod-2);}
int a[200010],f[200010];
signed main() {
    ios::sync_with_stdio(false);
    for(int i=1;i<=200000;i++)
        f[i]=(f[i-1]+inv(2*i*i%mod))%mod;
    int T=1;
    cin>>T;
    while(T--) {
        int n,cnt0=0,cnt1=0,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cnt0+=(a[i]==0);
        for(int i=1;i<=cnt0;i++) cnt1+=(a[i]==1);
        cout<<f[cnt1]*(n*(n-1)%mod)%mod<<endl;
    }
    return 0;
}