牛妹的位运算

思路

这题要求在 中找满足 且 的对数。

先搞清楚 到底意味着什么。两个数比大小，看的是最高位。AND 在某一位为 1，说明 a、b 在那一位都是 1；XOR 在某一位为 1，说明 a、b 在那一位不同。

所以条件成立的含义是：存在某个二进制位，a 和 b 在这一位上不同，并且在所有更高的位上，a 和 b 完全相同。换句话说，a 和 b 的最高不同位，要比它们的最高"都为1"的位更高。

再换个角度想：只要 ，考虑它们从高到低第一次出现不同的那一位。在这一位之上，a 和 b 完全相同，所以 AND 和 XOR 在那些更高位上的贡献一样。而在这个"第一次不同"的位上，XOR 为 1、AND 为 0，于是 XOR 一定大于 AND。

等等，这说明 只要 ，条件就一定成立！

验证一下： 时， 里满足 的对有 和 ，去掉 的只有 ，答案是 1。没问题。

时，总共有 个 的对，去掉 4 个 的，剩 6 个。但答案是 5？

哦， 不满足条件：，， 成立。那 ：，，，不满足！

所以上面的推理有漏洞。a 和 b 在最高不同位上，一个是 0 一个是 1，XOR 那一位为 1、AND 那一位为 0。但在更高位上，a 和 b 相同——如果那些相同的位都是 1，那 AND 在那些位上也是 1，跟 XOR 的 0 平手。关键在于最高不同位这一位上 XOR 赢了，但如果之前"都是1"的位已经让 AND 在更高处占了优势，那就不成立。

重新分析：条件 等价于——a 和 b 最高不同的那一位，比它们最高"都是1"的那一位更高。也就是说，在 a 和 b 第一次出现不同之前，它们在更高位上不能有共同的 1。

好，那我们来逐位分析。从最高位（第 位）到最低位（第 0 位），每一位上 a 和 b 的状态有四种：、、、。

对于满足条件的对，从高位往低位看，必须先出现一个"不同位"（ 或 ），然后后面的位就可以随便取了。在"不同位"出现之前，只能取 ——因为如果取了 ，AND 的最高位就定了，XOR 在更低位不可能超过它。

设第一个"不同位"出现在第 位（）：

  • 第 位以上的 位，每位只能是 ，共 1 种选法
  • 第 位上必须不同，有 和 两种
  • 第 位以下的 位，每位 4 种选法，共 种

再加上 的约束。注意到第 位上 意味着 在这一位确定， 意味着 在这一位确定。之后低位可以随意。但我们要 ，所以第 位如果取 ，则不管低位怎么取都有 ；如果取 ，则不管低位怎么取都有 。

也就是说第 位只能取 ，只有 1 种选法（不是 2 种）。

所以总数为：

$$

用快速幂计算 ，再乘以 3 的模逆元即可。

代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

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

int main() {
    long long k;
    cin >> k;
    long long inv3 = power(3, MOD - 2, MOD);
    long long ans = (power(4, k, MOD) - 1 + MOD) % MOD * inv3 % MOD;
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007L;

    static long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) res = res * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long k = sc.nextLong();
        long inv3 = power(3, MOD - 2, MOD);
        long ans = (power(4, k, MOD) - 1 + MOD) % MOD * inv3 % MOD;
        System.out.println(ans);
    }
}

MOD = 10**9 + 7
k = int(input())
ans = (pow(4, k, MOD) - 1 + MOD) % MOD * pow(3, MOD - 2, MOD) % MOD
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const MOD = 1000000007n;
    const k = BigInt(line.trim());
    function power(base, exp, mod) {
        let res = 1n;
        base %= mod;
        while (exp > 0n) {
            if (exp & 1n) res = res * base % mod;
            base = base * base % mod;
            exp >>= 1n;
        }
        return res;
    }
    const inv3 = power(3n, MOD - 2n, MOD);
    const ans = (power(4n, k, MOD) - 1n + MOD) % MOD * inv3 % MOD;
    console.log(ans.toString());
    rl.close();
});

复杂度

  • 时间复杂度：，快速幂的开销。
  • 空间复杂度：。