时间戳

首页 > 技术文章 > 「LNOI2022」盒

「LNOI2022」盒

crashed 2022-06-07 20:26 原文

题目

点这里看题目。

分析

设 \(p_j=\sum_{k=1}^ja_k,S=p_n\)。

一眼写出答案：

\[\begin{aligned} \sum_{j=1}^{n-1}w_j\sum_{k=0}^S|k-p_j|&\binom{k+j-1}{j-1}\binom{S-k+n-j-1}{n-j-1} \end{aligned} \]

然后只会 \(O(nm)\) 算。

实际上，把绝对值拆开之后，我们要着力解决的是：

\[\sum_{j=1}^{n-1}w_j\sum_{k=0}^{p_j}(p_j-k)\binom{k+j-1}{j-1}\binom{S-k+n-j-1}{n-j-1} \]

注意到，我们可以将 \(k\binom{k+j-1}{j-1}\) 变成 \(j\binom{k+j-1}{j}\)，而这个东西形式和 \(\binom{k+j-1}{j-1}\) 类似，所以我们最终只需要集中精力解决一个：

\[\sum_{j=1}^{n-1}c_j\sum_{k=0}^{p_j}\binom{k+j-1}{j-1}\binom{S-k+n-j-1}{n-j-1} \]

其中 \(c_j\) 是一个只和 \(j\) 相关的系数。

手玩一下，后面那个东西没有办法很好地得到一个通项。这个时候，我们就应当及时考虑其它角度切入。比如，如果通项求不出来，递推行不行呢？

虽然看起来这里只有一个外加参数 \(j\)，但是我们必须注意到，这个 \(p_j\) 实际上和 \(j\) 几乎一点关系没有，因此我们最好考虑两个变量递推。考虑：

\[f_{j,l}=\sum_{k=0}^l\binom{k+j-1}{j-1}\binom{S-k+n-j-1}{n-j-1} \]

首先，从 \(f_{j,l}\rightarrow f_{j,l+1}\) 是很容易的。注意到 \(p_j\) 和 \(j\) 同调，因而我们考虑从 \(f_{j,l}\rightarrow f_{j+1,l}\)。

构造组合意义

使用组合意义，但我自己先被消灭了。

为了得到一个比较良好的组合意义，我们最好先细致把玩一下对象。

如果我们去掉求和上界，那么这个和式很容易被化简：

\[\sum_{k\ge 0}\binom{k+j-1}{j-1}\binom{S-k+n-j-1}{n-j-1}=\binom{S+n-1}{n-1} \]

但是，反过来，去掉上界之后得到的是超集的结果，那么 \(f_{j,l}\) 必然是 \(\binom{S+n-1}{n-1}\) 某些地方被限制之后的结果。并且，我们还可以注意到 \(\binom{S+n-1}{n-1}\) 和 \(j\) 无关！因此，我们最好从 \(\binom{S+n-1}{n-1}\) 入手，来构造一下 \(f_{j,l}\) 的组合含义。

考虑 \(\binom{S+n-1}{n-1}\) 的基本含义：从 \([1,S+n-1]\) 的整数中选出 \(n-1\) 个互不相同的整数。不妨设这些整数从小到大为 \(q_1,q_2,\dots,q_{n-1}\)。那么，结合 \(j\)，我们发现 \(k\) 实际上是在枚举 \(q_j\)，而上界的含义即为 \(q_j\le l+j\)。

接着，从 \(f_{j,l}\) 到 \(f_{j+1,l}\) 是怎样变化的呢？我们修改了限制对象，现在得考虑 \(q_{j+1}\le l+j+1\)。而另一方面，我们延续上面的想法，讨论一下 \(q_j\le l+j\) 和 \(q_{j+1}\le l+j+1\) 之间的联系——容易发现后者为前者的充分条件。反过来，从 \(f_{j,l}\) 到 \(f_{j+1,l}\)，就只需要减去合乎 \(q_j\le l+j\) 而不合 \(q_{j+1}\le l+j+1\) 的 \(\{q_j\}_{1\le j<n}\) 即可——这也就意味着 \(q_j\le l+j,l+j+1<q_{j+1}\)。这个条件下，前 \(j\) 个和后 \(n-1-j\) 个完全独立开了，我们可以直接计算。因而：

\[f_{j+1,l}=f_{j,l}-\binom{l+j}{j}\binom{(S+n-1)-(l+j+1)}{n-j-1} \]

最后，可以 \(O(n+S)\) 地解决单组询问。

直接数学推导

组合数有很好的差分和求和形式，因此我们考虑利用这条性质，来拆开 \(f_{j+1,l}\) 中的组合数，以期得到 \(f_{j,l}\)，并计算剩下的系数。

为了方便，这里先做一下代换：设 \(u=n-j,v=S-k+u,w=k+j\)。则：

\[\begin{aligned} f_{j+1,l} &=\sum_{k=0}^l\binom{w}{j}\binom{v-2}{u-2}\\ &=\sum_{k=0}^l\left(\binom{w-1}{j}+\binom{w-1}{j-1}\right)\left(\binom{v-1}{u-1}-\binom{v-2}{u-1}\right)\\ &=f_{j,l}+\sum_{k=0}^l\binom{w-1}{j}\binom{v-1}{u-1}-\sum_{k=0}^l\binom{w}{j}\binom{v-2}{u-1}\\ &=f_{j,l}+\sum_{k=0}^{l-1}\binom{w}{j}\binom{v-2}{u-1}-\sum_{k=0}^l\binom{w}{j}\binom{v-2}{u-1}\\ &=f_{j,l}-\binom{l+j}{j}\binom{S-l+n-j-2}{n-j-1} \end{aligned} \]

恰好就和上面的组合意义对上了。

所以，还是数学推导好啊。不对，那为啥一开始我没看出来？

理论上来说，应该还剩下一个类似的 \(j\binom{k+j-1}{j}\) 亟待解决。不过，考虑到它的推导过程几乎完全一致，这里就略去不谈了。

最后，由于 \(j\) 和 \(p_j\) 都是单调的，我们可以直接维护 \(f_{j,l}\) 的值，进行某一维上的单步转移。单组复杂度为 \(O(n+S)\)。

小结：

  1. 首先，能想到递推这个角度，对我来说就很已经很恼火了。但是，我们必须注意到，计数问题中，一个和式的最后结果其实形式单一，基本上非通项即递推。因此，一条路走不通的时候，不要太怀疑，很有可能另一条就是明路

推荐阅读