玩自专题

牛客小白赛 18 J: Forsaken喜欢玩自走棋(SOS DP)

对于一个二进制,它的贡献必须加到它的子集里,这和SOS DP 的形式类似。 把每个输入的进制取反,整个过程也就反过来了:一个二进制,它的贡献必须加到包含它的集合里,即求子集和,这正是SOS DP的过程。 于是求一遍SOS DP,遍历 2 20 2^{20} 220 以内的二进制,找出值最大二进制值也最大的即可。 SOS DP (子集和DP)是类似高维前缀和的东西,由于它每一位只有0