AGC041D Problem Scores

pufanyi

题解

发布于：Mar 4, 2020

问存在多少个长度为 $n\,(2\le n\le 5000)$ 的单调不减序列 $a$，满足 $1\le a_i\le n$，且对于任意 $k\,(1\le k<n)$，都有：对任意大小为 $k$ 的子集 $S$ 和大小为 $k+1$ 的子集 $T$，满足 $\sum_{x\in S}A_x<\sum_{x\in T}A_x$。答案对大质数 $m$ 取模。

首先需要发现一个性质，就是如果 $k=\left\lfloor\frac{n}{2}\right\rfloor$ 的时候满足了，那么其他的 $k$ 都能满足。为什么呢？首先是对于每个 $k$，显然如果满足了 $\sum_{i=1}^{k+1}a_i\ge \sum_{i=n-k+1}^na_i$，就满足所有的 $S$ 和 $T$ 了。然后如果满足了 $k=\left\lfloor\frac{n}{2}\right\rfloor$ 的情况，如果 $k>\left\lfloor\frac{n}{2}\right\rfloor$，考虑到序列单调不降，左边加上一个较大的数，右边加上一个较小的数，那么不等式肯定仍然成立。否则，如果 $k<\left\lfloor\frac{n}{2}\right\rfloor$，其实就是左边减去一个较小的数，右边加上一个较大的数，不等式也仍然成立。

那这个东西有什么用呢，我们考虑对一波式子。首先我们需要去掉一个单调性，我们构造一个差分数组 $\Delta a_i=a_i-a_{i-1}$，为了不让 $\Delta a_1$ 奇怪，我们就让 $a_0=1$，这样子其实就是 $a_i=1+\sum_{i=1}^n\Delta a_i$，然后我们的式子就变成了：

$$\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor+1}\sum_{j=1}^i\Delta a_j\ge \sum_{i=n-\left\lfloor\frac{n}{2}\right\rfloor+1}^n\sum_{j=1}^i\Delta a_j$$

这个下取整感觉很难受，我们就直接将 $n$ 奇偶讨论好了：

当 $n$ 是奇数时，$\left\lfloor\frac{n}{2}\right\rfloor=\frac{n-1}{2}$，也就是原式就变成了：

$$\sum_{i=1}^{\frac{n+1}{2}}\sum_{j=1}^i\Delta a_j\ge \sum_{i=\frac{n+1}{2}+1}^n\sum_{j=1}^i\Delta a_j$$

两边都加个 $\sum_{i=1}^{\frac{n+1}{2}}\sum_{j=1}^i\Delta a_j$ 把右边给补一下：

$$2\sum_{i=1}^{\frac{n+1}{2}}\sum_{j=1}^i\Delta a_j\ge \sum_{i=1}^n\sum_{j=1}^i\Delta a_j$$

根据套路，我们需要把前面的 $\Sigma$ 拆掉，于是我们拆掉它：

$$2\sum_{i=1}^{\frac{n+1}{2}}\left(\frac{n+1}{2}-i+1\right)\Delta a_i\ge \sum_{i=1}^n\left(n-i+1\right)\Delta a_i$$

考虑我们将 $a_i$ 差分的目的，其实就是想把左边的式子减过去，然后合并起来：

$$\sum_{i=1}^nc_i\Delta a_i\le 0$$

其中

$$c_i= \begin{cases} i-2 & i\le \frac{n+1}{2}\\ n-i+1 & i>\frac{n+1}{2} \end{cases}$$

同样地，我们来考虑 $n$ 是偶数的情况：

$$\sum_{i=1}^{\frac{n}{2}}\sum_{j=1}^i\Delta a_j\ge \sum_{i=\frac{n}{2}+2}^n\sum_{j=1}^i\Delta a_j$$

补一补：

$$2\sum_{i=1}^{\frac{n}{2}}\sum_{j=1}^i\Delta a_j\ge \sum_{i=1}^n\sum_{j=1}^i\Delta a_j-\sum_{i=1}^{\frac{n}{2}+1}\Delta a_i$$

拆个 $\Sigma$：

$$2\sum_{i=1}^{\frac{n}{2}}\left(\frac{n}{2}-i+1\right)\Delta a_i\ge \sum_{i=1}^n\left(n-i+1\right)\Delta a_i-\sum_{i=1}^{\frac{n}{2}+1}\Delta a_i$$

写成 $\sum c_i\Delta a_i\le 0$ 的形式，可以得到：

$$c_i= \begin{cases} i-2 & i\le\frac{n}{2}\\ n-i & i=\frac{n}{2}+1\\ n-i+1 & i>\frac{n}{2}+1 \end{cases}$$

不难发现当 $i=\frac{n}{2}+1$ 时，$n-i=\frac{n}{2}-1=i-2$，所以：

$$c_i= \begin{cases} i-2 & i\le\frac{n}{2}+1\\ n-i+1 & i>\frac{n}{2}+1 \end{cases}$$

综合奇偶两个式子，我们均可以得到：

$$\sum_{i=1}^nc_i\Delta a_i\le 0$$

其中

$$c_i= \begin{cases} i-2 & i\le\left\lfloor\frac{n}{2}\right\rfloor+1\\ n-i+1 & i>\left\lfloor\frac{n}{2}\right\rfloor+1 \end{cases}$$

我们回到题目，除了这个条件，我们再回过头来看看有什么缺的条件，仔细找了找好像只有 $\sum\Delta a_i+1\le n$ 了。

于是我们考虑确定 $a_2\sim a_n$ 的值，然后回过头来看看有多少个符合条件的 $a_1$。

我们发现只有两个条件：

$$\begin{cases} a_1\le n-1-\sum_{i=2}^na_i\\ a_1\ge \sum_{i=2}^nc_ia_i \end{cases}$$

于是满足条件的 $a_1$ 个数就是：

$$\max\left(0, n-\sum_{i=2}^n\left(c_i+1\right)a_i\right)$$

我们令 $f_i$ 表示 $\sum_{j=2}^n\left(c_j+1\right)a_j=i$ 的方案数，那么最终的答案就是 $\sum_{i=0}^{n-1} (n-i)\cdot f_i$。

我们最后要做的一件事情就是计算 $f_i$ 了，不难发现其实就是一个背包，第 $i$ 个物品重量 $c_i$，可以选 $a_i$ 个，直接大力 dp 过去即可。

于是复杂度 $\mathcal{O}(n^2)$。

代码

更新于：Jul 2, 2023

DP

AtCoder