[AtCoder Grand Contest 060][C. Large Heap]

看了几篇题解都是从下往上（子树大小从小到大）推的，来整一个从上往下的。

题目链接：C - Large Heap

题目大意：称一个大小为 \(2^N-1\) 的排列是好排列当且仅当其满足对任意 \(1\le i\le 2^{N-1}-1\)，有 \(P_i<P_{2i}\) 且 \(P_i<P_{2i+1}\)。给定 \(N,A,B\)，问在所有的好排列中选取一个排列，其满足 \(P_{2^A}<P_{2^{B+1}-1}\) 的概率。

分析题意

\(P_i<P_{2i}\) 且 \(P_i<P_{2i+1}\) 这个限制一眼就是二叉树，那么把排列放到一个以 \(1\) 为根的满二叉树上，就可以把它看做是一个小根堆。题目要问的就是深度为 \(A\) 的在最左边的点 \(U\) 比深度为 \(B\) 的在最右边的点 \(V\) 小的概率，考虑使用动态规划解决此题。

状态设立与转移

考虑从小到大逐一确定每个数字所在位置的过程，一个位置被放上数字当且仅当其父亲上也有数字，那么答案就只与根节点到 \(U,V\) 这两个点上路径上的点有关。于是设 \(f_{i,j}\) 表示左边深度为 \(i\) 的点已经放了，右边深度为 \(j\) 的点还没放，且恰好放到 \(j-1\) 的概率。此时的状态对应的大小关系就是 \(P_{2^j-1}<P_{2^i}<P_{2^{j+1}-1}\)，最后答案即为 \(\sum_{i=1}^{B}f_{A,i}\)。

之所以要这么设立状态是因为，当我们在考虑下一个数字放哪的时候，我们需要明确目前参与“招标”的具体是哪两个点。如果仅仅只是知道左边深度为 \(i\) 的点小于右边深度为 \(j\) 的点，我们是难以保证左边的点其是不是已经在之前战胜了右边的点的祖先的。

考虑如何转移，\(f_{i,j}\) 所表示情况是：左边已经放到了深度为 \(i\) 的点，右边已经放到了深度为 \(j-1\) 的点。那么下一轮要参与 \(\text{PK}\) 的就是左边深度为 \(i+1\) 的点与右边深度为 \(j\) 的点。如果左边胜出则转移至 \(f_{i+1,j}\)，否则就会发生右边深度为 \(j\) 的点恰好小于左边深度为 \(i+1\) 的点的情况，那么考虑对称性，可以转移到 \(f_{j,i+1}\) 上。

考虑每次转移要乘上的概率系数，显然除了以这两个点为根的子树外，其它位置上的值并不会影响对应概率。那么当两子树大小分别为 \(x,y\) 时，这两个子树内分配数字的方案总共有 \(\binom{x+y}{x}\) 种。若钦定了最小值在左边这个大小为 \(x\) 的子树上，那么分配方案就有 \(\binom{x+y-1}{x-1}\)，计算得出对应概率系数就是 \(\frac{x}{x+y}\)。

常见错误

之前在想这题时陷入了一个误区，把这题扔给队友后他也和我出现了同样的问题，于是记录下来以示警戒。

一种常见的错误就是在设立状态时，直接令 \(g_{i,j}\) 表示左边深度为 \(i\) 的点比右边深度为 \(j\) 的点小的概率，然后用上述方式转移。这样会导致出错，比如在 \(n=3\) 时，可以得出 \(g_{1,2}=\frac{7}{8}\)，那么考虑从 \(g_{1,2}\) 转移到 \(g_{2,2}\) 的过程，会神奇的得出 \(g_{2,2}=g_{1,2}\times \frac{1}{2}=\frac{7}{16}\neq\frac{1}{2}\)，于是就寄了。

而寄的原因就是，如果 \(\text{DP}\) 时是直接考虑两棵子树的状态，那么在转移计算概率时相当于就是已经钦定了两个子树的状态，与无后效性原则相悖。这也是本人考虑从上往下一个个放数字的过程入手的原因。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define N 5050
#define LL long long
#define MOD 998244353
int n,a,b,f[N][N],sz[N],ans;
LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	sz[n-1]=1;
	f[1][1]=qow(2,MOD-2);
	for(int i=n-2;i>=0;i--)sz[i]=(2ll*sz[i+1]+1)%MOD;
	for(int s=2;s<2*n-2;s++)
	for(int i=1;i<n-1;i++){
		int j=s-i;
		if(j<1 || j>n-1)continue;
		int p=1ll*sz[i+1]*qow(sz[i+1]+sz[j],MOD-2)%MOD;
		f[i+1][j]=(f[i+1][j]+1ll*p*f[i][j])%MOD;
		p=(MOD+1-p)%MOD;
		f[j][i+1]=(f[j][i+1]+1ll*p*f[i][j])%MOD;
	}
	for(int i=1;i<=b;i++)ans=(ans+f[a][i])%MOD;
	printf("%d\n",ans);
}

计算概率时显然逆元是可以预处理的，不过时限充裕就懒得优化了（。

加上这一优化时间复杂度可以做到 \(O(n^2)\)。