题目传送门
题意:有一个 01 序列,每次可以选择两个元素,如果为逆序则交换,否则不变,无论是否交换都算一次操作。问排好序的期望操作次数。
容易想到使用 DP 计算,但状态并不是很好想。首先状态必须有单向性,必须有严格的 DP 顺序,于是我们可以想到用逆序对数来记录状态。然而,思考会发现并不可行。不仅是复杂度无法接受,仅用逆序对也无法完整地表示状态。实际上,我们可以用“未归位的数字个数”来作为状态。具体地,假设当前序列为 01101011,该序列一共有三个 0,所以前三位应该都是 0,而实际上有两个 1,就定义此时的“未归位的数字个数”为 2。这个状态的单向性显然,完整性也容易证明,因为只有“归位”的交换是有意义的,如果没有达到“归位”的效果,无论是否交换都是没有意义的。
做法 1
我们定义 f[i] 表示有 i 个“未归位的数字”时,要想排好序的期望步数。则我们可以考虑期望多少次操作之后能减少一个“未归位的数字”。一次操作“能减少”的方案数显然为左边 1 的个数乘右边 0 的个数,即 i2,所以“能减少”的概率 p1=n(n−1)/2i2=n(n−1)2i2,反之“不能减少”的概率即为 p2=1−p1=n(n−1)n(n−1)−2i2。于是,f[i]=j=0∑∞p2j⋅p1⋅(f[i−1]+j+1),其中 j 表示“失误”了多少次。我们考虑如何计算这个无穷级数:
f[i]=j=0∑∞p2j⋅p1⋅(f[i−1]+j+1)=p1j=0∑∞p2j⋅(f[i−1]+j+1)=p1(j=0∑∞p2j⋅(f[i−1]+1)+j=0∑∞p2j⋅j)
我们令 x=f[i−1]+1,则第一项简化为 j=0∑∞p2j⋅x=xj=0∑∞p2j。设 S=j=0∑∞p2j,则 p2S=j=1∑∞p2j,两式相减得 (1−p2)S=p20=1,即 S=1−p21。对于第二项同理,令 S′=j=0∑∞p2j⋅j,则 p2S′=j=1∑∞p2j(j−1),两式相减得 (1−p2)S′=j=1∑∞p2j=S=1−p21,即 S′=(1−p2)21。于是:
f[i]=p1(1−p2f[i−1]+1+(1−p2)21)
此即为 DP 方程。
By cxm1024
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #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,概率为 n(n−1)2i2;如果没有选中该选的数,则情况不变,而额外增加了一步,为 f[i]+1,概率为 n(n−1)n(n−1)−2i2。你可能会有疑问,我们还没有算出 f[i] 来,怎么能转移呢?事实上,如果我们列出了转移方程:f[i]=n(n−1)2i2(f[i−1]+1)+n(n−1)n(n−1)−2i2(f[i]+1),则会发现这转化为了一个简单的解方程问题,直接解出 f[i] 即可:
f[i]=(1−n(n−1)n(n−1)−2i2)f[i]=n(n−1)2i2⋅f[i]=f[i]=n(n−1)2i2⋅f[i−1]+n(n−1)n(n−1)−2i2⋅f[i]+1n(n−1)2i2⋅f[i−1]+1n(n−1)2i2⋅f[i−1]+1f[i−1]+2i2n(n−1)
在此方法下,最终的转移方程如此的简单,只是一个前缀和的形式。
By cxm1024
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #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; }
|