题解 | #牛妹的位运算#

题目链接

牛妹的位运算

题目描述

给定一个正整数 $k$ ，要求在区间 $[0, 2^k)$ 内寻找满足以下所有条件的非负整数对 $(a, b)$ 的数量：

$a \le b$
$(a \;\text{AND}\; b) < (a \;\text{XOR}\; b)$

结果需要对 $10^9 + 7$ 取模。

解题思路

这是一个位运算相关的计数问题。核心在于理解并简化条件 $(a \;\text{AND}\; b) < (a \;\text{XOR}\; b)$ 。

条件转换

让我们从二进制表示的角度来分析这个不等式。设 $C = a \;\text{AND}\; b$ ， $D = a \;\text{XOR}\; b$ 。为了比较 $C$ 和 $D$ 的大小，我们通常从它们的最高位开始比较。

设 $p$ 是 $a$ 或 $b$ 中最高有效位（Most Significant Bit, MSB）的位置。也就是说， $p$ 是使得 $a$ 的第 $p$ 位或 $b$ 的第 $p$ 位为 1 的最大下标。对于所有 $j > p$ ， $a$ 和 $b$ 的第 $j$ 位都为 0。

对于所有 $j > p$ ， $C$ 和 $D$ 的第 $j$ 位显然也都是 0。
现在考虑第 $p$ 位：
- 因为 $p$ 是最高有效位， $a$ 和 $b$ 在第 $p$ 位上不能都为 0。
- 情况 1： $a$ 和 $b$ 在第 $p$ 位上分别为 1 和 0（或 0 和 1）。
  - $C$ 的第 $p$ 位是 $1 \;\text{AND}\; 0 = 0$ 。
  - $D$ 的第 $p$ 位是 $1 \;\text{XOR}\; 0 = 1$ 。
  - 在这种情况下， $D$ 在它与 $C$ 的第一个不同位上是 1，所以 $D > C$ 。
- 情况 2： $a$ 和 $b$ 在第 $p$ 位上都为 1。
  - $C$ 的第 $p$ 位是 $1 \;\text{AND}\; 1 = 1$ 。
  - $D$ 的第 $p$ 位是 $1 \;\text{XOR}\; 1 = 0$ 。
  - 在这种情况下， $C$ 在它与 $D$ 的第一个不同位上是 1，所以 $C > D$ 。

由此我们得出结论：不等式 $(a \;\text{AND}\; b) < (a \;\text{XOR}\; b)$ 成立，当且仅当在 $a$ 和 $b$ 的最高公共有效位 $p$ 上，它们的值不相同。这等价于说， $a$ 和 $b$ 的最高有效位在不同的位置上。为方便起见，我们定义 $\text{msb}(x)$ 为 $x$ 的最高有效位的索引（例如 $\text{msb}(6) = \text{msb}(110_2) = 2$ ），并定义 $\text{msb}(0) = -1$ 。那么，原条件就等价于 $\text{msb}(a) \neq \text{msb}(b)$ 。

组合计数

现在问题转化为：计算满足 $0 \le a \le b < 2^k$ 且 $\text{msb}(a) \neq \text{msb}(b)$ 的数对 $(a, b)$ 的数量。

我们可以分情况讨论：

当 $a=0$ 时： $\text{msb}(a) = -1$ 。条件变为 $-1 \neq \text{msb}(b)$ ，这意味着 $b$ 不能为 0。又因为 $a \le b$ ，所以 $0 \le b$ 恒成立。因此， $b$ 可以是 $[1, 2^k - 1]$ 内的任何整数。这种情况下的数对数量为 $2^k - 1$ 。
当 $a > 0$ 时：设 $j = \text{msb}(a)$ ， $i = \text{msb}(b)$ 。条件 $a \le b$ 意味着 $j \le i$ 。条件 $\text{msb}(a) \neq \text{msb}(b)$ 意味着 $j \neq i$ 。结合两者，我们必须有 $j < i$ 。

我们对 $i$ 和 $j$ 进行枚举：
- $i$ 可以从 $1$ 取到 $k-1$ 。
- 对于每个固定的 $i$ ， $j$ 可以从 $0$ 取到 $i-1$ 。
对于固定的 $i$ 和 $j$ （其中 $j < i$ ）：
- 满足 $\text{msb}(b) = i$ 的 $b$ 的数量为 $2^i$ (即从 $2^i$ 到 $2^{i+1}-1$ )。
- 满足 $\text{msb}(a) = j$ 的 $a$ 的数量为 $2^j$ (即从 $2^j$ 到 $2^{j+1}-1$ )。
- 因为 $j < i$ ，任何满足 $\text{msb}(a)=j$ 的 $a$ 都小于任何满足 $\text{msb}(b)=i$ 的 $b$ ，所以 $a \le b$ 恒成立。
- 因此，对于固定的 $i, j$ ，有 $2^i \cdot 2^j$ 对 $(a, b)$ 。
总数量为 $\sum_{i=1}^{k-1} \sum_{j=0}^{i-1} 2^i \cdot 2^j = \sum_{i=1}^{k-1} 2^i (\sum_{j=0}^{i-1} 2^j)$ 。内部的和是等比数列求和： $\sum_{j=0}^{i-1} 2^j = 2^i - 1$ 。所以，和式变为 $\sum_{i=1}^{k-1} 2^i(2^i - 1) = \sum_{i=1}^{k-1} (4^i - 2^i) = \sum_{i=1}^{k-1} 4^i - \sum_{i=1}^{k-1} 2^i$ 。再次使用等比数列求和公式：
- $\sum_{i=1}^{k-1} 4^i = \frac{4(4^{k-1}-1)}{4-1} = \frac{4^k-4}{3}$
- $\sum_{i=1}^{k-1} 2^i = \frac{2(2^{k-1}-1)}{2-1} = 2^k-2$ 这部分的数量为 $\frac{4^k-4}{3} - (2^k-2)$ 。

合并结果

总数 = (情况1的数量) + (情况2的数量)
$= (2^k - 1) + \left(\frac{4^k-4}{3} - (2^k-2)\right)$
$= 2^k - 1 + \frac{4^k-4}{3} - 2^k + 2$
$= \frac{4^k-4}{3} + 1 = \frac{4^k-4+3}{3} = \frac{4^k-1}{3}$ 。

我们只需要计算 $(4^k-1) \cdot 3^{-1} \pmod{10^9+7}$ 即可。这需要用到快速幂和模逆元。

代码

c++
java
python

#include <iostream>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 1000000007;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 1000000007;
        base = (base * base) % 1000000007;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, 1000000007 - 2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k;
    cin >> k;
    
    long long p4k = power(4, k);
    long long numerator = (p4k - 1 + 1000000007) % 1000000007;
    long long inv3 = modInverse(3);
    
    long long ans = (numerator * inv3) % 1000000007;
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static long power(long base, long exp) {
        long res = 1;
        long mod = 1000000007;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    static long modInverse(long n) {
        long mod = 1000000007;
        return power(n, mod - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        long mod = 1000000007;

        long p4k = power(4, k);
        long numerator = (p4k - 1 + mod) % mod;
        long inv3 = modInverse(3);

        long ans = (numerator * inv3) % mod;

        System.out.println(ans);
    }
}

def power(base, exp):
    res = 1
    mod = 10**9 + 7
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

def mod_inverse(n):
    mod = 10**9 + 7
    return power(n, mod - 2)

def solve():
    k = int(input())
    mod = 10**9 + 7
    
    p4k = power(4, k)
    numerator = (p4k - 1 + mod) % mod
    inv3 = mod_inverse(3)
    
    ans = (numerator * inv3) % mod
    print(ans)

solve()

算法及复杂度

算法：数学 + 组合计数 + 模运算。通过分析位运算性质将问题转化为计数问题，并通过推导数学公式得到封闭解。
时间复杂度：计算结果主要依赖于快速幂运算，其时间复杂度为 $\mathcal{O}(\log k)$ 。
空间复杂度：算法只需要常数个变量，空间复杂度为 $\mathcal{O}(1)$ 。