题解：2024牛客暑期多校第1场——B [A Bit More Common]

英文题干

Given two integers 𝑛 and 𝑚, among all the sequences containing 𝑛 non-negative integers less than , you need to count the number of such sequences 𝐴 that there exists two different non-empty subsequence of 𝐴 in which the bitwise AND of the integers is 1.

Note that a non-empty subsequence of a sequence 𝐴 is a non-empty sequence that can be obtained by deleting zero or more elements from 𝐴 and arranging the remaining elements in their original order. Two subsequences are different if they are composed of different locations in the original sequence.

Since the answer may be very large, output it modulo a positive integer 𝑞.

The bitwise AND of non-negative integers 𝐴 and 𝐵, (𝐴 AND 𝐵) is defined as follows:

• When (𝐴 AND 𝐵) is written in base two, the digit in the 's place ( is 1 if those of 𝐴 and 𝐵 are both 1, and 0 otherwise.

For example, we have (4 AND 6 = 4) (in base two: (100 AND 110 = 100)).

Generally, the bitwise AND of 𝑘 non-negative integers is defined as (…(( AND ) AND ) AND … AND ) and we can prove that this value does not depend on the order of .

Input:

The only line contains three integers , and .

Output:

Output a line containing an integer, denoting the answer.

中文题干

给定两个整数 𝑛 和 𝑚，在所有包含 𝑛 个非负整数且小于 的序列中，您需要计算这样的序列 𝐴 的数量，其中存在两个不同的非空子序列，这两个子序列的整数按位与为 1。

请注意，序列 𝐴 的非空子序列是指通过删除零个或多个元素并按照剩余元素的原始顺序排列而获得的非空序列。如果两个子序列由原始序列中的不同位置组成，则它们是不同的。

由于答案可能非常大，因此请对正整数 𝑞 取模后输出。

非负整数 𝐴 和 𝐵 的按位与操作（𝐴 AND 𝐵）定义如下：

• 当将 (𝐴 AND 𝐵) 用二进制表示时， 位（ 上的数字为 1，如果 𝐴 和 𝐵 的对应位均为 1，则为 1，否则为 0。

例如，我们有 (4 AND 6 = 4)（以二进制表示为：(100 AND 110 = 100)）。

一般来说， 𝑘 个非负整数 的按位与操作被定义为 (…(( AND ) AND ) AND … AND )，我们可以证明这个值不依赖于 的顺序。

思路

本题是A题的衍生，区别是把满足要求的子序列数量从1增加到2

1. 由于A题的铺垫，我们很自然地想到：B题答案=(A题答案)－(只有1个子序列满足条件的情况)。下面只需考虑如何求后者。

2. 只有1个子序列满足条件，说明A题中所选的这 k 个奇数的二进制表示在某些位只有一个数是0，我们把这些位称为“特殊位”。

3. 记这k个奇数总共对应了t个“特殊位”，那么总方案数是：

• ：n 个数中选 k 个作为奇数
• ：剩余的 n-k 个偶数除了最后一位之外，剩下 m-1 位均可选0或1。
• ：选中的 k 个奇数将它们全部表示为 m 位二进制。然后把每一位的 k 个01看成一个二进制数串。这个串不能全是1，否则该位的 k 个1取 AND和 之后必然是1，其他情况都是可以的。

AC代码

时间复杂度：O()