异或树[jzoj6707]
题意
题解
显然这是一道DP题。看起来似乎只能从高位到低位考虑。
假设有些点的最高位为 $0$，剩下的点最高位为 $1$，那么这些点形成了两个连通块。
这两个连通块内部先做一次最小生成树，然后之间需要连一条边权最小的边链接这两个连通块。
现在我们先来算，假设你考虑到某一位 $i$（从 $0$ 开始），有两块的大小是 $k,l$，这时候中间这条边的权值的期望*方案数是多少，记这个数为 $g_{i,k,l}$。
然而这个 $g$ 是无法直接算的。考虑转换最小值，有一个经典的套路，要算一个随机变量 $x$ 的期望，那么可以通过以下转换：
$$E(x)=\sum_{i=0} i[P(x=i)]=\sum_{i=1}[P(x\geq i)]$$
我们转换成求这条权值最小的边大于等于某个数 $j(j< 2^i)$ 的方案数，也就是所以跨过两个块的边都大于等于这个 $j$ 的方案数。设这个方案数为 $f_{i,j,k,l}$。
现在只需要考虑 $f$ 如何计算。
进行大力分类讨论：
$k=0$ 或 $l=0$
这时候为了方便其他 $f$ 的计算，可以令 $f_{i,j,k,l}$ 直接表示为所有的方案数，即 $2^{(i+1)(k+l)}$。
$j$ 的第 $i$ 位为 $1$
这时候 $k,l$ 都大于 $0$ 了，那么这两个块的最高位异或后必须为 $1$，也就是一个块的最高位全是 $0$ ，令一个的最高位全是 $1$，这样的方案数有两种，然后还需要看 $j$ 除去第 $i$ 位后的结果，也就是 $f_{i-1,j\oplus 2^i,k,l}$。
$j$ 的第 $i$ 位为 $0$
此时，这两个块的最高位就没有什么限制了，也就是块内的最高位可以不相同。那么，就需要分别枚举两个块有多少个最高位为 $0$ 的，设为 $u,v$，一共有 $\binom{k}{u}\times \binom{l}{v}$ 种选法，对于 $j$ 的限制，显然不需要考虑不同块且最高位不同的点，方案数为 $f_{i-1,j,u,v}\times f_{i-1,j,k-u,l-v}$。
然后大力转移就好了。需要注意 $i=0$ 时的边界。
现在你已经求出了所有的 $g_{i,k,l}$。
最后需要将这些 $g_{i,k,l}$ 转换成答案。
我们可以再来一个DP，设 $h_{i,j}$ 表示考虑到第 $i$ 位（从 $0$ 开始），一共 $j$ 个点时的答案之和。
然后还是按照最高位分两块，枚举其中一块的点数 $k$，则有：
$$h_{i,j}=\sum_{k=0}^j\binom{j}{k}\left (2^{i(j-k)}h_{i-1,k}+2^{ik}h_{i-1,j-k}+[k>0,j>k](g_{i-1,k,j-k}+2^i\times 2^{ij})\right )$$
最后面的 $[k>0,j>k]$ 是需要保证两个块都有点，才能有一条跨过两块的边。
时间复杂度 $O(mn^42^m)$，有超级多个 $\frac{1}{2}$ 的常数，因此卡卡常，减小一下取模的次数就过了。
注意 $n=1$ 的特判。
程序
1 |
|