CF643F Bears and Juice 题解

被黑题吓死了。

如何计算答案

首先需要注意酒桶和熊都是区分的，不要读错题目意思了。

不妨先来考虑一些简单的情况。

考虑 的情况。对于这种情况，实际上我们只能接受醉倒 头熊，因为要保证至少一头熊清醒。由于醉倒的熊的个数和用掉的床位是相等的，直接将 对 取 即可。

• 对于只有一个床位的情况：挨个试过去即可。 天最多可以区分 桶。
• 对于只有一天，但是允许醉倒很多熊：直接二进制分组。

然而其余的状态其实并不是很好解决。不妨先考虑有 头熊，最多允许醉倒 头熊， 天内，能否区分 桶饮料。

你发现，由于醉倒的熊需要占据相同个数的床位，因此我们只需要记录其中一个即可。

我们现在的问题变成了，在还能醉倒 头熊，剩下 天的情况下，能否区分 桶饮料。

我们继续观察我们每天可以做什么操作。实际上是下面这个东西：

• 对于每个还醒着的熊 ，分配一个桶的集合 。
• 这一天结束的时候，
  • 如果第 头熊醒着，说明 里没有酒，酒在 的补集里。此时将 补和候选集合取交集即可。
  • 如果第 头熊醉倒了，说明 里有酒。此时将候选集合和 取交集。

最后会剩下来一个候选集合 。对于集合里的饮料，就我们目前拥有的信息没办法区分它们，并且我们也没有任何额外的能表明“某些桶更有可能是酒”之类的信息。

因此这实际上构成了一个子问题，可以递归的求解。

为了能区分出这么多饮料，我们需要保证以下几点：

• 对于每一种可能出现的结果（每一头熊是否醉倒）及其结果 ，满足：
  • 醉倒的熊的个数 小于等于 。
  • 可以在醉倒 头熊，剩下 天的情况下区分出 桶酒。

形式化的，令 表示能否在剩下 个床位， 天内区分 桶饮料。

我们每次的操作实际上是：

• 对于第 头熊，将饮料集合 划分为不交的集合 和 。熊 喝 里的酒。
• 将每天晚上的结果记成一个长度为 的 字符串 ， 当且仅当熊 喝完酒醉倒了。
• 构造候选集合 。
• 醉倒的熊的个数 。

对于每个可能出现的 ，满足 为真，那么 也为真。

我们发现一个问题：我们的 里记录的是布尔值，在这种情况下是十分浪费的。我们希望 可以记录更加有用的信息。

我们注意到一个性质：如果你能区分 桶饮料，那么对于任何 ，你也能区分 桶饮料。

结论是显然的，对于方案的构造可以考虑补上若干桶一定不是酒的饮料转化成大小为 时的情况，转化成实际方案时如果遇到了补上的酒就直接忽略。

因此，对于相同的 ，合法的 是一段前缀。我们在 数组里面记录最远的前缀即可。

也就是说，让 表示剩下 个床位， 天最多可以区分多少桶饮料。

根据二进制分组的想法，对于所有可能出现的结果 ，其候选集合 必然两两不交，且并集等于全集。因为这集合天然构成了一个划分，对于每一种酒可能在的位置都被恰好包含了一次。

我们反过来考虑，对于每个结果 ，为 分配大小，显然其大小最大为 。结果就是 。对于醉倒的熊超过床位的情况，这个时候集合大小可以被看为 。由于必然存在一桶酒，这种情况必然不会出现，因此这样的转移是自洽的。如果你对这个说法不太放心，也可以用数学归纳法严格证明。

反过来构造方案也是容易的，如果 ，就将 加入 ，否则加入 。假设最终的候选集合是 ，我们递归的使用 的最优方案解决即可。不同的 会在第一天产生不同的结果，因而这些方案之间互相不会影响。

然后我们发现这个转移之和 有关，也就是 。这个的上界是床位。我们不妨枚举这个做转移，合法的集合个数是 。将这乘上 加起来就是这个位置的答案。

然后我们发现这个转移之和 有关，也就是 。这个的上界是床位。我们不妨枚举这个做转移，合法的集合个数是 。将这乘上 加起来就是这个位置的答案。

也就是：

但是还没结束！这个暴力复杂度是 （组合数可以预处理）。不足以通过啊？

更快的计算方法

考虑打表找规律。此时打出来的表会十分有规律。固定床位 ，将 dp 数组看成关于天数的函数。接下来的 。

时，函数恒为 。 是等差数列。如果你对 做二阶差分，发现都是相同的。

此时你可以直接猜 的时候是一个最多 次多项式然后拉格朗日插值！然而你发现 逆元并不好处理。

不过没关系！我们求出的是一段连续的值，因此可以差分之后再前缀和回去。

由于 是次数不超过 的多项式，因此差分 次之后为常数。因此可以这样还原整个序列。

具体的，求出前 项的值，差分 次，记录每次差分前的第一个数。之后做 遍前缀和即可。复杂度 。

我们接下来考虑归纳的证明这个结论。

引理 ： 是 次多项式。

这点其实非常容易理解。这就是说，此时不能接受任何熊醉倒，因而只能区分 桶饮料。

引理 ：若对于 满足 是不超过 次的多项式，那么 是不超过 次的多项式。

我们把我们的 dp 转移用新的符号重新写出来。

提出来一个 ：

首先右侧的 实际上是原多项式平移了一下，仍然是一个关于 的多项式。并且平移不改变次数，因此右侧多项式最高次数就是 。

这实际上是说： 的差分是一个不超过 次的多项式。因此 是一个不超过 次的多项式。

另外本题的做法也比较多，这篇和这篇也是我觉得比较有意思的做法，