一道插入 DP 题。
分析
这一类型的 DP 大多是对许多段的维护，各个段之间的要求较弱或没有，一般都很难搞。
先把概率转成计数。
观察题面，我们可以考虑维护一条从上到下类似扫描线的东西，每次计算下移一格的贡献。很明显，在坐标轴上画出图像，应当由数个峰组成。从上往下扫描就会形成一些联续段，考虑 DP 维护。
设 \(f_{i,j,k,p,q}\) 表示讨论了前 \(i\) 大的值，它们组成了 \(j\) 个连续段，已获得了 \(k\) 的贡献，左右两侧是否取满了。
讨论第 \(i\) 大放在了哪里，分类转移。
-
新增一段。\(f_{i,j,k,p,q}\times(j+1-p-q)\rightarrow f_{i+1,j+1,k+(2\times j-p-q),p,q}\)
-
新增靠边的一段。\(f_{i,j,k,p,q}\rightarrow f_{i+1,j+1,k+(2\times j-p-q),p+0/1,q+1/0}\)
-
增长一段。\(f_{i,j,k,p,q}\times(2\times j-p-q)\rightarrow f_{i+1,j,k+(2\times j-p-q),p,q}\)
-
合并两段。\(f_{i,j,k,p,q}\times(j-1)\rightarrow f_{i+1,j-1,k+(2\times j-p-q),p,q}\)
-
合并一段与边界。\(f_{i,j,k,p,q}\rightarrow f_{i+1,j,k+(2\times j-p-q),p+0/1,q+1/0}\)
运算过程注意精度，至于输出（借用了一下另一位的），从高到低判断应该输出什么即可。
#include<bits/stdc++.h>
using namespace std;
const int N=110,mod=1e9+7;
int n,m,q;
struct A{
double f[N][N*N][2][2],g[N][N*N][2][2],ans;
int main(){
f[1][0][0][0]=f[1][0][0][1]=f[1][0][1][0]=f[1][0][1][1]=1;
for(int i=2;i<=n;++i){
for(int j=1;j<i;++j)
for(int k=0;k<=i*i;++k)
for(int p=0;p<2;++p)
for(int q=0;q<2;++q){
g[j][k][p][q]=f[j][k][p][q];
f[j][k][p][q]=0;
}
for(int j=1;j<i;++j)
for(int k=0;k<=i*i;++k)
for(int p=0;p<2;++p)
for(int q=0;q<2;++q){
int cnt=k+2*j-p-q;
double d=g[j][k][p][q];
if(j+1-p-q>0) f[j+1][cnt][p][q]+=(j+1-p-q)*d/i;
if(!p) f[j+1][cnt][1][q]+=d/i,f[j][cnt][1][q]+=d/i;
if(!q) f[j+1][cnt][p][1]+=d/i,f[j][cnt][p][1]+=d/i;
if(2*j-p-q>0) f[j][cnt][p][q]+=d*(2*j-p-q)/i;
if(j>1) f[j-1][cnt][p][q]+=d*(j-1)/i;
}
}
for(int i=m;i<=n*n;++i) ans+=f[1][i][1][1];
if(ans + 1e-14 >= 1){cout << "1." << string(q,'0') << endl; return 0;}
cout << "0.";
ans *= 10;
for(int i = 1 ; i <= q ; ++i){
cout << (int)(ans + (q == i) * 0.5);
ans = (ans - (int)ans) * 10;
}
return 0;
}
}m1;
struct B{
__float128 f[N][N*N][2][2],g[N][N*N][2][2],ans;
int main(){
f[1][0][0][0]=f[1][0][0][1]=f[1][0][1][0]=f[1][0][1][1]=1;
for(int i=2;i<=n;++i){
for(int j=1;j<i;++j)
for(int k=0;k<=i*i;++k)
for(int p=0;p<2;++p)
for(int q=0;q<2;++q){
g[j][k][p][q]=f[j][k][p][q];
f[j][k][p][q]=0;
}
for(int j=1;j<i;++j)
for(int k=0;k<=i*i;++k)
for(int p=0;p<2;++p)
for(int q=0;q<2;++q){
int cnt=k+2*j-p-q;
__float128 d=g[j][k][p][q];
if(j+1-p-q>0) f[j+1][cnt][p][q]+=(j+1-p-q)*d/i;
if(!p) f[j+1][cnt][1][q]+=d/i,f[j][cnt][1][q]+=d/i;
if(!q) f[j+1][cnt][p][1]+=d/i,f[j][cnt][p][1]+=d/i;
if(2*j-p-q>0) f[j][cnt][p][q]+=d*(2*j-p-q)/i;
if(j>1) f[j-1][cnt][p][q]+=d*(j-1)/i;
}
}
for(int i=m;i<=n*n;++i) ans+=f[1][i][1][1];
if(ans + 1e-14 >= 1){cout << "1." << string(q,'0') << endl; return 0;}
cout << "0.";
ans *= 10;
for(int i = 1 ; i <= q ; ++i){
cout << (int)(ans + (q == i) * 0.5);
ans = (ans - (int)ans) * 10;
}
return 0;
}
}m2;
int main(){
scanf("%d%d%d",&n,&m,&q);
if(q<=8) m1.main();
else m2.main();
return 0;
}