两个 common 题
A
最后一位是关键，我们可以证明：序列合法与序列中奇数元素的与和是 等价。
枚举奇数个数，确保确保每个前 位在这些奇数中都有一个零即可。
B
同样，最后一位是关键。
定义合法子序列为与和为 的子序列。
至少有两个合法子序列的方案数等于至少有一个合法子序列的方案数减恰好有一个合法子序列的方案数。
“至少有一个合法子序列的方案数”在 A 题中被我们秒了，我们现在需要求“减恰好有一个合法子序列的方案数”。
还是枚举奇数个数，可以发现，题目中要求的两个合法子序列肯定有一个是由所有奇数组成的子序列。我们定义在奇数中，前 位恰好只有一个数在这一位是
的位为特殊位，“减恰好有一个合法子序列的方案”即为这些奇数中每一个数都被分到一个特殊位（这样删掉任何一个奇数都无法找出合法子序列）。
在枚举奇数个数的循环中，我们枚举特殊位数量（从奇数个数到 ），之后计算“减恰好有一个合法子序列的方案数”，这题就做完了，记得非特殊位并不是乱来的，他们在奇数中至少有两个
（这个的计算方法还是整体减部分，所有的方案数减恰好没有
和只有一个
的方案数）。
关于将特殊位分给奇数的方案数：
设特殊位有 个，奇数有
个，
为方案数，则递推式为
，分为放在某一类和用一个元素替换掉之前的一个类并把那一个类放到当前的新类两种情况。
京公网安备 11010502036488号