2022-2023:teams:eager_to_embrace_the_seniors_thigh:1h
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2022-2023:teams:eager_to_embrace_the_seniors_thigh:1h [2022/08/11 17:59] 11231123 [题解] |
2022-2023:teams:eager_to_embrace_the_seniors_thigh:1h [2022/08/11 17:59] (当前版本) 11231123 [题解] |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| 注意到 $m$ 非常大，所以直接做背包是没有前途的。这时候我们注意到 $a_i2^k$ 这样的一个物品是不会影响到总和的二进制最低的 $k$ 位的，所以我们考虑按照 $2^0$ 到 $2^{59}$ 这个顺序来对这些物品进行DP。 | 注意到 $m$ 非常大，所以直接做背包是没有前途的。这时候我们注意到 $a_i2^k$ 这样的一个物品是不会影响到总和的二进制最低的 $k$ 位的，所以我们考虑按照 $2^0$ 到 $2^{59}$ 这个顺序来对这些物品进行DP。 | ||
| - | 我们定义 $dp_{i,j,0/1}$ 表示已经选完 $2^i$ 一类的物品，总和 $S$ 满足 $\lfloor \frac{S}{2^{i+1}} \rfloor = j$ ，且 $S\%2^i$ 是否严格大于 $m\%2^i$ 的方案数。 | + | 我们定义 $dp_{i,j,0/1}$ 表示已经选完 $2^i$ 一类的物品，总和 $S$ 满足 $\lfloor \frac{S}{2^{i+1}} \rfloor = j$ ，且 $S\%2^{i+1}$ 是否严格大于 $m\%2^{i+1}$ 的方案数。 |
2022-2023/teams/eager_to_embrace_the_seniors_thigh/1h.1660211942.txt.gz · 最后更改: 2022/08/11 17:59 由 11231123
