ABC481 G Half-Baked

· · 题解

观前提示：这个不是什么阳间做法。

设每个 cake 都是一个随机变量 X_i。

$$\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}f_i$$ 其中 $f_i=\sum_{|T|=i,T\subseteq[n]}\mathbb{E}(\max(\{X_t|t\in T\}))$，也就是所有大小为 $i$ 的子集的 $\max$ 的期望。 如果求出了 $f$，那个 minmax 容斥的式子是可以差卷积的，没有什么难度。主要难度在这个变态的 $f$ 怎么求。 先不管期望，我们先求出所有大小为 $k$ 的方案的 $\max$ 的和 $g_k$，这个转化到 $f_k$ 也就是除以 $2^k$ 的事。 给所有的 $A_i,B_i$ 一起排序，要求相同值的 $A,B$，$A$ 排在 $B$ 前面。我们称排完序的序列是 $C$，考虑最大值在哪里取到，我们考虑 $C_i$ 是某个方案最大值。那么比 $i$ 大的位置肯定是不用考虑了，比 $i$ 小的位置里，有一些 cake 是 $A,B$ 都在的，有一些只有 $A$ 在，$B$ 在比 $i$ 大的位置。我们称前一类 cake 的数量是 $x$，后一类是 $y$。我们需要在这 $x+y$ 里选出 $k-1$ 个，并确定他们的选择 $A,B$ 的方案。显然只有 $x$ 里的有的挑，$y$ 的只能选 $A$。于是方案数的生成函数是： $$s(x,y)=(1+2z)^x(1+z)^y$$ 那么 $C_i$ 对 $g_k$ 的贡献就是 $C_i[z^k]s(x,y)$。 我们注意到对于一个 $i$，$x,y$ 是不变的，而且相邻的 $i$ 对应的 $x,y$ 好像不会变化太多。具体的，如果 $C_i$ 是一个 $A$，那么经过 $i$ 以后，$y\leftarrow y+1$；如果是一个 $B$，那么 $x \leftarrow x+1,y\leftarrow y-1$。需要注意的是在 $B$ 的时候，$C_i$ 对 $g_k$ 的贡献需要在 $y\leftarrow y-1$ 之后计算（也就是说，依次执行的是 $y\leftarrow y-1$，计算贡献，$x \leftarrow x+1$）。 放在生成函数上考虑，也就是： $$s_{i}=\begin{cases}(1+z)s_{i-1}& C_i\in A\\\frac{1+2z}{1+z}s_{i-1} & C_i \in B\end{cases}$$ 其中 $s_i$ 表示在 $i$ 处的 $x,y$ 对应的 $s(x,y)$。 再考虑到贡献的计算（设 $G(z)=\sum_{i=1}g_{i}z^{i-1}$，偏移一位是因为必须要选 $C_i$ 当前这一个），我们可以得到如下流程： - 令 $S(z)=1$。 - 遍历 $i=1\dots 2n$，对于当前的 $C_i$： - 如果 $C_i$ 是一个 $A$，那么 $G\leftarrow G+C_iS, S\leftarrow(1+z)S$。 - 如果 $C_i$ 是一个 $B$，那么 $S\leftarrow\frac{1}{1+z}S, G\leftarrow G+C_iS, S\leftarrow(1+2z)S$。 注意此处的 $C_i\in B$ 的情况，呼应了上文的计算贡献的位置。 暴力模拟即可得到 $O(n^2)$ 做法。 考虑优化。这个递推一看就很矩阵！ - 如果 $C_i$ 是一个 $A$： $$\begin{bmatrix}G\\S\end{bmatrix}\leftarrow\begin{bmatrix}1&C_i\\0&1+z\end{bmatrix}\begin{bmatrix}G\\S\end{bmatrix}$$ - 如果 $C_i$ 是一个 $B$： $$\begin{bmatrix}G\\S\end{bmatrix}\leftarrow\begin{bmatrix}1&\frac{C_i}{1+z}\\0&\frac{1+2z}{1+z}\end{bmatrix}\begin{bmatrix}G\\S\end{bmatrix}=\frac{1}{1+z}\begin{bmatrix}1+z&C_i\\0&1+2z\end{bmatrix}\begin{bmatrix}G\\S\end{bmatrix}$$ 把所有 $\frac{1}{1+z}$ 提到外面去就行了，里面分治矩阵乘法即可。复杂度 $O(n\log^2 n)$，常数一百万。 最后记得把 $2^n$ 乘回去。