https://www.luogu.com.cn/problem/P2012

https://www.luogu.com.cn/record/157386025

5个点MLE

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    private static final BigInteger P = BigInteger.valueOf(1000000000);
    private static final BigInteger PHI = BigInteger.valueOf(400000000);
    private static final BigInteger[] TABLE = new BigInteger[]{
            BigInteger.ZERO, BigInteger.ZERO, BigInteger.ZERO, BigInteger.ZERO,
            BigInteger.valueOf(24), BigInteger.valueOf(480), BigInteger.valueOf(7680), BigInteger.valueOf(107520)
    };
    private static BigInteger[] pw1 = new BigInteger[32769];
    private static BigInteger[] pw2 = new BigInteger[32769];
    private static BigInteger[] pw3 = new BigInteger[32769];
    private static BigInteger[] pw4 = new BigInteger[32769];

    static {
        pw1[0] = BigInteger.ONE;
        pw2[0] = BigInteger.ONE;
        pw3[0] = BigInteger.ONE;
        pw4[0] = BigInteger.ONE;
        pw1[1] = BigInteger.valueOf(2);
        for (int i = 2; i <= 32768; ++i) {
            pw1[i] = pw1[i - 1].multiply(BigInteger.valueOf(2)).mod(P);
        }
        pw2[1] = pw1[32768];
        for (int i = 2; i <= 32768; ++i) {
            pw2[i] = pw2[i - 1].multiply(pw2[1]).mod(P);
        }
        pw3[1] = BigInteger.valueOf(12);
        for (int i = 2; i <= 32768; ++i) {
            pw3[i] = pw3[i - 1].multiply(BigInteger.valueOf(12)).mod(P);
        }
        pw4[1] = pw3[32768];
        for (int i = 2; i <= 32768; ++i) {
            pw4[i] = pw4[i - 1].multiply(pw4[1]).mod(P);
        }
    }

    private static BigInteger solve(BigInteger n) {
        int intedValue = n.and(BigInteger.valueOf(32767)).intValue();
        BigInteger x = pw1[intedValue]
                .multiply(pw2[n.shiftRight(15).intValue()]).mod(P);
        BigInteger y = x.multiply(x).mod(P);
        BigInteger res = BigInteger.valueOf(81).multiply(pw3[intedValue])
                .multiply(pw4[n.shiftRight(15).intValue()]).mod(P)
                .subtract(BigInteger.valueOf(64).multiply(x).multiply(y).mod(P))
                .add(BigInteger.valueOf(6).multiply(y).add(P).mod(P));
        return n.and(BigInteger.ONE).equals(BigInteger.ONE) ?
                res.compareTo(y) < 0 ? res.subtract(y).add(P) : res.subtract(y) :
                res.add(y).compareTo(P) >= 0 ? res.add(y).subtract(P) : res.add(y);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            BigInteger n = scanner.nextBigInteger();
            if (n.equals(BigInteger.ZERO)) break;
            BigInteger x = n.compareTo(PHI) >= 0 ? n.mod(PHI).add(PHI) : n;
            BigInteger result = x.compareTo(BigInteger.valueOf(8)) < 0 ? TABLE[x.intValue()] : solve(x.subtract(BigInteger.valueOf(4)));
            System.out.println(result.mod(P));
        }
        scanner.close();
    }
}