题解 | 牛妹的位运算

import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/12
 * @description   BGN86 牛妹的位运算
 */

//注释里面异或和指数都是用的符号 ^
public class Main {
	//1.题目意思解析，首先对于a ^ b > a & b(假设a > b)肯定是看最高位的1，如果a, b最高位1相同a ^ b < a & b, 否则a的最高位1在b前面a ^ b > a & b
    //所以就是对于每个b（i）, 求对应的最高位1前于b的a(j > i)有多少个然后求和%1e9+7
    //那么怎么求呢？可以看出2 ^ 0, 2 ^ 1, 2 ^ 2,......,  2 ^ n之间依次左移，所以可以得出为（2 ^ (k + 1) - 2 ^ k）* (2 ^ n - 2 ^ (k + 1)),化简之后
    //(2 ^ k) * (2 ^ n - 2 ^ (k + 1))注意k属于0 ~ n - 2求和，同时还要加上对于0元素的额外处理（0不属于2 ^ x, x为自然数）

    //2.题目意思理解完之后还有一个问题就是2 ^ 1e5太大了，没办法直接计算，由于是计算%1e9+7的结果，中间需要提前处理
    //(a * b) % base = (a % base + b % base) % base
    //(a - b) % base = (tmp = a % base - b % base) > 0 ? tmp : tmp + base
    //上面两步a = x * base + a % base, 可以试着推一下
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //区间为[0, 2 ^ n)
        int n = in.nextInt();

        //mods[i]表示2 ^ i % base的结果
        long base = (long) 1e9 + 7;
        long[] mods = new long[n + 5];
        for (int i = 0; i <= n; i++) {
            mods[i] = i > 0 ? (2 * mods[i - 1]) % base : 1;
        }
        long result = 0, tmp;
	  	//计算0 ~ n - 2部分
        for (int i = 0; i <= n - 2; i++) {
            result += (mods[i] * ((tmp = mods[n] - mods[i + 1]) > 0 ? tmp : base + tmp)) % base;
        }
	  	//对于b = 0额外处理
        result += mods[n] - 1 > 0 ? mods[n] - 1 : base + mods[n] - 1;
        System.out.println(result % base);
    }
}