「IOI2020」装饼干 题解

问题转化

我们有 $k$ 种饼干，类型 $i$ 的饼干：

• 每块口味值 = $2^i$
• 库存数量 = $a_i$
• 要装 $x$ 袋饼干，每袋口味值都是 $y$

设每袋中类型 $i$ 的饼干块数为 $t_i$，则：

• $y = \sum_{i=0}^{k-1} t_i \cdot 2^i$
• 所有袋子加起来，类型 $i$ 的饼干总数 = $x \cdot t_i \le a_i$
• 所以 $t_i \le \lfloor a_i / x \rfloor$

令 $b_i = \lfloor a_i / x \rfloor$，问题转化为：

有多少个整数 $y$ 可以表示为 $y = \sum_{i=0}^{k-1} t_i \cdot 2^i$，其中 $0 \le t_i \le b_i$。

---

关键观察

这是一个有限制的二进制表示问题。如果没有限制 $t_i \le b_i$，那么所有 $y$ 在 $[0, \sum b_i 2^i]$ 范围内连续。但由于每个位的"数字" $t_i$ 有上限 $b_i$，会导致一些值无法表示，形成"空洞"。

我们需要高效地统计所有可表示的 $y$ 值数量。

---

数位 DP 思路

从低位 ($i=0$) 到高位 ($i=k-1$) 逐位考虑，因为高位依赖于低位的进位。

状态定义

设 $dp[i][c]$ = 考虑完前 $i$ 位（位 $0$ 到 $i-1$），向第 $i$ 位的进位为 $c$ 时，已经能形成的不同 $y$ 的取值数目。

这里"进位" $c$ 的含义是：在计算 $y$ 的二进制表示时，第 $i-1$ 位向第 $i$ 位进位的值。

状态转移

当我们处理第 $i$ 位时：

• 该位在 $y$ 的二进制表示中的值 = $(c + t_i) \bmod 2$
• 向下一位的进位 = $\lfloor (c + t_i) / 2 \rfloor$

其中 $t_i$ 是我们为这一位选择的数字，满足 $0 \le t_i \le b_i$。

对于每个可能的 $t_i$，我们计算：

• 新进位 $c' = \lfloor (c + t_i) / 2 \rfloor$
• 当前位值 $bit = (c + t_i) \bmod 2$

由于我们是从低位向高位 DP，当前位值一旦确定，就固定了 $y$ 的这一位，不会改变。

初始状态

$dp[0][0] = 1$（还没有考虑任何位，进位为 0，只有 1 种情况）

最终答案

考虑完所有 $k$ 位后，进位 $c$ 必须为 0（否则 $y$ 的值会超出我们考虑的位数范围），所以答案是 $dp[k][0]$。

---

状态数优化

直接按上述方法 DP，状态数可能很大，因为进位 $c$ 理论上可以达到 $\sum b_i$，这太大了。

重要优化观察

实际上，进位 $c$ 的范围是有限的。因为：

• 在第 $i$ 位，最大可能的 $t_i = b_i$
• 最大进位来自前一位 $c_{max}$ 加上 $b_i$ 再除以 2
• 所以进位大小是 $O(\max b_i)$ 级别的

更精确地说，进位 $c$ 的范围是 $[0, \max_{j \le i} b_j + 1]$。由于 $b_i = \lfloor a_i / x \rfloor$，且 $a_i \le 10^{18}$，$x \ge 1$，所以 $b_i \le 10^{18}$，但实际计算中进位不会太大。

进一步优化

我们可以不显式存储所有状态，而是维护一个"可达的进位状态集合"。由于每步进位状态数量不会太多（通常 $O(k)$），我们可以用 map 或类似结构存储 $(进位, 方案数)$ 对。

---

算法步骤

1. 预处理 $b_i = \lfloor a_i / x \rfloor$
2. 初始化：states = {0: 1}（进位 0 有 1 种方式）
3. 对于 $i = 0$ 到 $k-1$：
   • 创建新状态字典 new_states
   • 对于当前每个状态 (carry, count)：
     • 对于 $t_i = 0$ 到 $b_i$：
       • 计算总合 = $carry + t_i$
       • 新进位 = $\lfloor 总合 / 2 \rfloor$
       • 当前位值 = $总合 \bmod 2$（这个用于确定 $y$ 的唯一性，但 DP 中我们只关心进位）
       • 如果当前位值固定，那么所有导致相同新进位和相同"历史决策"的状态会合并
       • 将 new_states[新进位] += count
   • states = new_states
4. 最终答案是 states[0]（进位为 0 的状态数）

---

复杂度分析

• 外层循环：$k \le 60$
• 内层状态数：理论上是 $O(\max b_i)$，但经过优化后实际运行中状态数通常 $O(k)$
• 每个状态考虑 $b_i+1$ 种选择，但 $b_i$ 可能很大

实际实现中，我们不需要枚举 $t_i$ 从 $0$ 到 $b_i$，而是可以数学计算转移，将复杂度优化到 $O(k \cdot M)$，其中 $M$ 是同时存在的状态数。

---

总结

这道题的核心是：

1. 将问题转化为有限制的二进制表示问题
2. 使用从低位到高位的数位 DP
3. 关键状态是"进位"而非具体的 $y$ 值
4. 通过状态合并和数学优化控制复杂度