题解：P13791 「CZOI-R6」抽奖

不错的计数题目，但是场上想出来的是斜率优化的形式，没有优化的可能了，赛后看了计数的做法茅厕顿开，写个题解记录一下。

我们考虑在抽奖机存在时间长度固定的情况下我们获取的收益是什么。首先我们获得的钱仅取决于最后一次抽奖的时间，因为每天的 $p$ 都增加 $\frac 1n$。

那么我们可以发现最优策略其实就是根据 $n,w$ 选择一些抽奖的固定时间点 $a_1,a_2,\dots,a_m$（设 $a_{m+1}=n+1$，$a_0=0$），对每个 $1\le n^\prime\le n$ 进行抽奖，取其收益期望的期望。由于这里乘了 $n^2$ 那就是收益和的和。

考虑如何计算总贡献。对于一对相邻的 $(a_i,a_{i+1})$，考虑 $n^\prime\in[a_i,a_{i+1})$，抽中的钱都是 $\frac{a_i}nw$。因此我们的总收益就是
$$
n^2\cdot\sum_{i=1}^m\dfrac{a_{i+1}-a_i}{n}\cdot\dfrac{a_iw}{n}=w\sum_{i=0}^ma_i(a_{i+1}-a_i)
$$
那么我们花费的钱数是什么呢？考虑在 $a_i$ 抽奖的花费是 $\frac{n}{n-a_i+1}$，而对于每一个 $n^\prime\ge a_i$，我们都需要在 $a_i$ 处花费，因此 $a_i$ 会有 $n-a_i+1$ 次花费贡献，加起来就是
$$
n^2\cdot\dfrac1n\sum_{i=0}^m\dfrac{n}{n-a_i+1}\cdot(n-a_i+1)=n^2m
$$
哦这是个只与 $m$ 有关的定值。

因此答案就是
$$
w\sum_{i=0}^ma_i(a_{i+1}-a_i)-n^2m
$$
我们考虑对它做一些变形，设 $d_i=\Delta a_i=a_{i+1}-a_i$，有
$$
\begin{aligned}
2\sum_{i=0}^m a_id_i&=2\sum_{i=0}^md_i\sum_{j=0}^{i-1}d_j\\
&=2\sum_{0\le i<j\le m}d_id_j=\bigg(\sum_{i=0}^m d_i\bigg)^2-\sum_{i=0}^md_i^2
\end{aligned}
$$
我们知道 $\sum_{i=0}^md_i=a_{m+1}=n+1$，因此要最大化原式的值就是最小化 $\sum_{i=1}^md_i^2$，而这是简单的，只需要让 $d_i$ 的极差 $\le 1$。证明考虑两个差 $\ge 2$ 的元素 $a<b$，让 $a$ 加 $1$，让 $b$ 减 $1$，答案的变化量是 $2a+1-(2b-1)=2(a-b)+2<0$。

因此我们发现最终的 $b_i$ 中有 $x=\left\lfloor\dfrac{n+1}{m+1}\right\rfloor$ 和 $y=\left\lfloor\dfrac{n+1}{m+1}\right\rfloor+1$ 两种数，且其各自的个数是确定的，对于给定的 $m$ 可以 $O(1)$ 求答案。

现在的做法是 $O(tn)$ 的，无法通过。我们发现当 $\left\lfloor\dfrac{n+1}{m+1}\right\rfloor$ 是定值的时候，$x,y$ 的出现次数 $c_x=m+1-(n+1)\bmod (m+1)$ 和 $c_y=(n+1)\bmod (m+1)$ 都是 $m$ 的一次函数。因此最终的答案最多是关于 $m$ 的二次函数。

二次函数的最大值是很好求的，但是要分类讨论开口是否向上。但事实上我们有
$$
\begin{aligned}
\dbinom{c_x}{2}x^2+\dbinom{c_y}{2}y^2+xyc_xc_y&=\dfrac12x^2c_x^2+\dfrac12y^2c_y^2+xyc_xc_y-\dfrac12(x^2c_x+y^2c_y)\\
&=\dfrac12\left[(xc_x+yc_y)^2-x^2c_x-y^2c_y\right]
\end{aligned}
$$
考虑到 $xc_x+yc_y=n+1$，因此上式为一次函数，所以最值就是端点的最值，直接数论分块做即可，复杂度 $O(t\sqrt n)$。

**UPD.** 感谢 @kooG 指出，答案函数实际上有比上面提出的更加强的性质，事实上设 $F(M)$ 表示 $m=M$ 时的答案，则 $F(M)$ 在 $M\in[0,n]$ 上是凸的，因此找其最大值只需要一次二分即可解决，复杂度 $O(t\log n)$。

:::info[对于 $F(M)$ 凸性的证明]

在上面的分析中我们已经知道 $F(M)$ 的图像由若干段直线构成，因此 $F(M)$ 上凸，就等价于随着 $\left\lfloor\dfrac{n+1}{m+1}\right\rfloor$ 的降低，函数 $\dbinom{c_x}{2}x^2+\dbinom{c_y}{2}y^2+xyc_xc_y$ 的斜率在降低，而这个函数的斜率仅与 $\left\lfloor\dfrac{n+1}{m+1}\right\rfloor$ 的值有关，不妨设带着变量 $C=\left\lfloor\dfrac{n+1}{m+1}\right\rfloor$ 写出斜率的表达式。

用 $C$ 将上面的变量 $x,y,c_x,c_y$ 表示出来有
$$
x=C,\quad y=C+1
$$
$$
c_x=(m+1)-(n+1)+C(m+1)=(C+1)m-n+C
$$
$$
c_y=(m+1)-c_x=-Cm+n-C+1
$$
在上面我们已经知道了 $\dbinom{c_x}{2}x^2+\dbinom{c_y}{2}y^2+xyc_xc_y=\dfrac12\left[(n+1)^2-x^2c_x-y^2c_y\right]$，因此我们现在只关注一次函数部分 $x^2c_x+y^2c_y$，即证其斜率随着 $C$ 单调递减即可，而展开有
$$
\begin{aligned}
x^2c_x+y^2c_y&=C^2[(C+1)m-n+C]+(C+1)^2(-Cm+n-C+1)\\
&=[C^2(C+1)-C(C+1)^2]m-(2C+1)(C-n)+(C+1)^2
\end{aligned}
$$
我们只关注斜率，有 $k=C^2(C+1)-C(C+1)^2=-C(C+1)$，在 $C>-\dfrac12$ 时单调递减，因此完成了对于 $F(M)$ 上凸性的证明。

:::

正在渲染内容...