理论基础

• (xy) ⊙ p=[(x ⊙ p)(y ⊙ p)] ⊙ p
• (x + y) ⊙ p=[(x ⊙ p) + (y ⊙ p)] ⊙ p

第一个式子网上没有搜到证明过程，自己手写了个大概（这里的 7 5 3 可以替换成上式的 x y p）：

快速幂算法

import java.util.Scanner;

public class Main {
    private static final int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int base = scanner.nextInt();    // 输入底数
        int exponent = scanner.nextInt(); // 输入指数
        System.out.println(fastPower(base, exponent));
    }

    /**
     * 快速幂算法：计算 (base^exponent) % MOD
     * @param base 底数（可以是任意整数）
     * @param exponent 指数（非负整数）
     * @return 计算结果
     */
    public static int fastPower(int base, int exponent) {
        long result = 1;
        long currentBase = base % MOD; // 初始底数取模，避免负数问题

        // 处理负数底数的情况（确保余数非负）
        if (currentBase < 0) {
            currentBase += MOD;
        }

        // 快速幂核心算法
        while (exponent > 0) {
            if ((exponent & 1) == 1) { // 当前二进制位为1
                result = (result * currentBase) % MOD;
            }
            currentBase = (currentBase * currentBase) % MOD; // 底数平方
            exponent >>= 1; // 右移一位（指数除以2）
        }

        // 处理 exponent = 0 的情况（任何数的0次幂为1）
        return (exponent == 0) ? 1 % MOD : (int) result;
    }
}

简化版：计算 2^n （ base 可以修改，不考虑 base 为负数的情况）

    private int pow(int base, int exponent) {
        long res = 1;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exponent >>= 1;
        }
        return (int) res % MOD;
    }

更加简化版，如果底数为 2，并且用上位运算的左移操作：

public void pretreatment() {
		// f 相当于一个预处理数组，计算所有 2 ^ n
    f[0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        f[i] = (f[i - 1] << 1) % P;
    }
}