出题人有几个妈妈，敢这样出题？

前面是一些简单的经典部分。

考虑把序列 $p$ 拍到平面直角坐标系上，其中第 $i$ 个点的坐标为 $(i,p_i)$，相邻两个点之间有一条连线，于是题目给出的要求相当于每条连线的纵坐标之差的和不小于 $m$。

考虑从小往大依次加入所有 $p_i$。设前 $i$ 个点的连线形成了 $k$ 个连续段，则每个连续段的左侧和右侧都会覆盖纵坐标为 $[p_i,p_i+1]$ 的部分，对答案造成 $2k$ 的贡献。特殊地，如果一个连续段被放在了最左段的位置，则其左侧不会对答案造成贡献，右侧同理。

基于上面的推导，考虑在特判 $n=1$ 的情况后 dp：设 $f_{i,j,k,c}$ 表示，考虑前 $i$ 个数的相对大小与连线关系，此时有 $j$ 个连续段，目前对答案的总贡献为 $k$，且被钦定放在两侧的连续段有 $c$ 个的概率。设 $k'=k+2j-c$，初始化 $f_{0,0,0,0}=1$，转移考虑分类讨论：

• 增加一个新的连续段：
  • 在两侧增加一个新的连续段，$f_{i,j+1,k',c+1} \leftarrow f_{i,j+1,k',c+1}+\dfrac{2-c}i\times f_{i-1,j,k,c}$；
  • 在中间增加一个新的连续段，$f_{i,j+1,k',c} \leftarrow f_{i,j+1,k',c}+\dfrac{j+1-c}i\times f_{i-1,j,k,c}$；
• 延续一个旧的连续段：
  • 在两侧延续一个旧的连续段，$f_{i,j,k',c+1} \leftarrow f_{i,j,k',c+1}+\dfrac{2-c}i\times f_{i-1,j,k,c}$；
  • 在中间延续一个旧的连续段，$f_{i,j,k',c} \leftarrow f_{i,j,k',c}+\dfrac{2j-c}i\times f_{i-1,j,k,c}$；
• 合并两个旧的连续段，$f_{i,j-1,k',c}\leftarrow f_{i,j-1,k',c}+\dfrac{j-1}i\times f_{i-1,j,k,c}$。

答案即为 $\sum\limits_{k=m}^{n^2} f_{n,1,k,2}$。使用滚动数组优化，时间复杂度 $\mathcal O(n^4)$，空间复杂度 $\mathcal O(n^3)$。

然后就是一些色情的部分了。

由于本题 $K\le30$，精度要求高，所以需要使用 __float128 计算 $f$。交一发，诶，怎么 TLE 了？

仔细阅读原题面：

对于 $30\%$ 的数据，$N \le 10$。 对于另外 $30\%$ 的数据，$K \le 3$。 对于另外 $30\%$ 的数据，$K \le 8$。 对于另外 $10\%$ 的数据，$N \le 50$。 对于 $100\%$ 的数据，$N \le 100$，$K \le 30$，$0 \le M \le 2147483647$。

注意到 $30\%+30\%+30\%+10\%=100\%$，不存在顶满数据范围的子任务。也就是说，当 $\boldsymbol{K \gt 8}$ 时满足 $\boldsymbol{N \le 50}$。

于是你发现出题人的妈妈消失了，数据点分治一下，$K \le 8$ 时使用 long double 计算 $f$ 即可。

const int N=105,M=5055,mod=1e9+7;
int n,m,k;
namespace Sub1{
	__float128 f[2][N][M][3],ans;
	void out(__float128 ans,int k){
		int tot=ans;printf("%d.",tot);
		while(k--){
		    ans=(ans-tot*1.0)*10.0;
		    if(!k) ans=ans+0.5;
		    tot=ans;printf("%d",tot);
		}
		printf("\n");
	}
	void solve(){
		if(m>=M) return out(0,k),void();
		if(n==1) return out(m==0,k),void();
		f[0][0][0][0]=1;
		for(int i=1;i<=n;i++){
			int ii=i&1;
			for(int j=0;j<=i;j++) for(int k=0;k<M;k++) for(int c=0;c<=2;c++) f[ii][j][k][c]=0;
			for(int j=0;j<i;j++){
				for(int k=0;k<M;k++){
					for(int c=0;c<=2;c++){
						int kk=k+2*j-c;
						if(kk>M) continue;
						if(c<2) f[ii][j+1][kk][c+1]+=(2-c)*f[ii^1][j][k][c]/i;
						f[ii][j+1][kk][c]+=(j+1-c)*f[ii^1][j][k][c]/i;
						if(j>0&&c<2) f[ii][j][kk][c+1]+=(2-c)*f[ii^1][j][k][c]/i;
						if(j>0) f[ii][j][kk][c]+=(2*j-c)*f[ii^1][j][k][c]/i;
						if(j>0) f[ii][j-1][kk][c]+=(j-1)*f[ii^1][j][k][c]/i;
					}
				}
			}
		}
		for(int k=m;k<M;k++) ans+=f[n&1][1][k][2];
		out(ans,k);
	}
}
namespace Sub2{
	long double f[2][N][M][3],ans;
	void out(long double ans,int k){
		int tot=ans;printf("%d.",tot);
		while(k--){
		    ans=(ans-tot*1.0)*10.0;
		    if(!k) ans=ans+0.5;
		    tot=ans;printf("%d",tot);
		}
		printf("\n");
	}
	void solve(){
		if(m>=M) return out(0,k),void();
		if(n==1) return out(m==0,k),void();
		f[0][0][0][0]=1;
		for(int i=1;i<=n;i++){
			int ii=i&1;
			for(int j=0;j<=i;j++) for(int k=0;k<M;k++) for(int c=0;c<=2;c++) f[ii][j][k][c]=0;
			for(int j=0;j<i;j++){
				for(int k=0;k<M;k++){
					for(int c=0;c<=2;c++){
						int kk=k+2*j-c;
						if(kk>M) continue;
						if(c<2) f[ii][j+1][kk][c+1]+=(2-c)*f[ii^1][j][k][c]/i;
						f[ii][j+1][kk][c]+=(j+1-c)*f[ii^1][j][k][c]/i;
						if(j>0&&c<2) f[ii][j][kk][c+1]+=(2-c)*f[ii^1][j][k][c]/i;
						if(j>0) f[ii][j][kk][c]+=(2*j-c)*f[ii^1][j][k][c]/i;
						if(j>0) f[ii][j-1][kk][c]+=(j-1)*f[ii^1][j][k][c]/i;
					}
				}
			}
		}
		for(int k=m;k<M;k++) ans+=f[n&1][1][k][2];
		out(ans,k);
	}
}
void solve(){
	cin>>n>>m>>k;
	if(k>8) Sub1::solve();
	else Sub2::solve();
}

请给 https://qoj.ac/problem/10766 点 downvote 谢谢喵。