Ptz Winter 2020 Day6 D Split in Sets

详细化 pb 的题解。

感性理解一下，把大数字单独放在一个盒子里，好像总不是太亏。

感性理解，和后面基本没关系。

假设所有数字里最高位是 $2^b$ ，且只有不超过 $k-1$ 个数字有 $2^b$ 。可以发现把它们每个单独放一个盒子一定是严格最优解：假设 $x_1,y$ 一个盒子， $x2$ 一个盒子，且 $x_1,x_2<2^b\le y$ 。由于 $x_1 +x_2 = x_1$ OR $x_2+x_1$ AND $x_2$ ，把 $x_1,x_2$ 放一起只会亏掉 $x_1$ OR $x_2$ ，严格小于 $y$ 。其他情况也可以用类似方式证明。

于是直接记录有 $2^b$ 的数的个数 $cnt$ ，将有 $2^b$ 的 $a_i$ 加进答案并从序列中删去，方案数则增加 $\binom{k}{cnt}\times cnt!$ ， $k\to k-cnt$ 。

而如果超过 $k-1$ 个数字有 $2^b$ ，同样可以证明 $<2^b$ 的数字必然处于同一个盒子内。此时直接把它们合并成一个数字，那么无论怎么分配都会有 $k-1$ 个盒子能贡献 $2^b$ ，于是 $b$ 这一位就可以删掉了。

先特判全部都有 $2^b$ ，直接全部将答案加上 $k\times 2^b$ ，全部数减去 $2^b$ 。

否则将所有没有 $2^b$ 的数并成一个数（注意不直接算进答案），类似地加贡献，减去 $2^b$ ，再继续算。

最后可能剩下若干个数和盒子。问题就是若干个有标号小球放进若干个有标号非空盒子方案数，这是一个斯特林数问题，搜一下通项公式解决。

Ptz Winter 2020 Day6 D Split in Sets

感谢您的支持，我会继续努力的!