date: 2021.01.23 ??:??-??:??

practice link

题目大意：有若干堆石子，每次可以取若干堆合并在一起，代价为合并后堆的大小。但是，堆数必须在 $L$ 和 $R$ 之间。求最小代价。

题解：显然每次合并时都会取最小的那几堆。假设两次相邻的合并分别取了 $x$ 堆和 $y$ 堆，若 $x>y$ 或 $x\le y$ 但是 $x-1$ 和 $y+1$ 合法，那么可以证明交换 $x,y$ 或者 $x-1,y+1$ 这样合并一定更优：

• 若 $\sum_{i=1}^{x}a_{i}\le a_{x+y}$，那么前者代价为 $\sum_{i=1}^{x}a_{i}+\sum_{i=1}^{x+y-1}a_{i}$，后者代价为 $\sum_{i=1}^{x-1}a_{i}+\sum_{i=1}^{x+y-1}a_{i}$。此后两个序列变得相同。因此 $x-1,y+1$ 更优。
• 否则，若 $\sum_{i=1}^{x-1}a_{i}\le a_{x+y}$，那么前者合并再次的代价为 $\sum_{i=1}^{x}a_{i}+\sum_{i=x+1}^{x+y}a_{i}$，后者合并两次代价为 $\sum_{i=1}^{x-1}a_{i}+\sum_{i=1}^{x+y-1}a_{i}$。后者代价更小。而合并完成之后，前者得到了 $\sum_{i=1}^{x}a_{i}$ 与 $\sum_{i=x+1}^{x+y}a_{i}$，后者得到了 $\sum_{i=1}^{x+y-1}a_{i}$ 与 $a_{x+y}$。由于 $a_{x+y}<\sum_{i=1}^{x}a_{i}$，且 $a_{x+y}\le\sum_{i=x+1}^{x+y}a_{i}$，因此后者的序列前缀和总是小于前者。可以证明在这一前提下，在任意的合并树下，后者的代价总比前者要优。因此 $x-1,y+1$ 更优。
• 否则，即 $\sum_{i=1}^{x-1}a_{i}>a_{x+y}$，那么前者合并再次的代价为 $\sum_{i=1}^{x}a_{i}+\sum_{i=x+1}^{x+y}a_{i}$，后者合并两次代价为 $\sum_{i=1}^{x-1}a_{i}+\sum_{i=x}^{x+y}a_{i}$。两者相同。而合并完成之后，前者得到了 $\sum_{i=1}^{x}a_{i}$ 与 $\sum_{i=x+1}^{x+y}a_{i}$，后者得到了 $\sum_{i=1}^{x-1}a_{i}$ 与 $\sum_{i=x}^{x+y}a_{i}$。若 $x\le y$，显然 $\sum_{i=1}^{x-1}a_{i}\le\sum_{i=1}^{x}a_{i}$ 且 $\sum_{i=1}^{x-1}a_{i}\le\sum_{i=x+1}^{x+y}a_{i}$，与上一种情况相同。而若 $x>y$，考虑交换 $x,y$，并且不妨钦定第二种情况先合并成 $\sum_{i=1}^{y}a_{i}$ 与 $\sum_{i=y+1}^{x+y}a_{i}$，容易证明这样还是更优。

因此合并的过程一定可以表示成 $L,L,L,\ldots,L,t,R,R,R,\ldots,R$。考虑两个序列 $A$ 和 $B$，其中 $B$ 的 $R$ 更多/$L$ 更少。显然可以从 $A$ 通过一些 $-1/+1$ 操作得到 $B$，$B$ 更优。

确定序列后，可以用一个队列直接暴力模拟，老题了。

题目大意：有 $n$ 颗石子排成一个环，从石子 $1$ 开始遍历，每遇到一颗石子，有 $p$ 的概率把它删除。对于石子 $c$，问它第 $1,2,\ldots,n$ 个被删除的概率。

题解：先讲一个等下要用的式子。令 $x=(1-p)^{t}$。那么

$$ \begin{aligned} &\sum_{t=0}^{+\infty}x^{e}\\ =&\sum_{t=0}^{+\infty}\left((1-p)^{e}\right)^{t}\\ =&\frac{1}{1-(1-p)^{e}} \end{aligned} $$

找到一个很妙的做法。考虑容斥，设 $f_{i}$ 表示 $c$ 后面恰有 $i$ 个石子的概率，那么

$$ \begin{aligned} f_{i}=\sum_{|T|\ge i,T\in\{1,2,\ldots,n\}-\{c\}}(-1)^{|T|-i}{|T|\choose i}g_{T} \end{aligned} $$

其中 $g_{T}$ 表示 $T$ 中石子都在 $c$ 之后的概率。

那么我们只需要考虑 $T\cup\{c\}$ 这个集合，甚至只需要关心 $T$ 中有几个在 $[1,c-1]$，有几个在 $[c+1,n]$ 即可。

设有 $i$ 个在 $[1,c-1]$，$j$ 个在 $[c+1,n]$，那么这样的 $T$ 有 ${c-1\choose i}{n-c\choose j}$ 个，合法的概率为（设 $c$ 在第 $t$ 轮删除）：

$$ \begin{aligned} &\sum_{t=0}^{+\infty}\left((1-p)^{t+1}\right)^{i}\left((1-p)^{t}\right)^{j+1}p\\ =&\frac{p(1-p)^{i}}{1-(1-p)^{i+j+1}} \end{aligned} $$

显然可以卷积求出 $g$，然后再卷积求出 $f$ 即可。