题解 | 小红的好数组

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case

            int n = in.nextInt();
            int k = in.nextInt();
            // 偶数个数
            int oddNum = k / 2;
            // 奇数个数
            int evenNum = k - oddNum;
            int mod = 1000000007;

            // 四种情况
            long ans = 0;
            ans = 1l * power(oddNum, n / 3, mod) * power(evenNum, n - n / 3, mod) % mod;
            ans = ans + 1l * power(oddNum, (n + 1) / 3, mod) * power(evenNum, n - (n + 1) / 3, mod) % mod;
            ans = ans + 1l * power(oddNum, (n + 2) / 3, mod) * power(evenNum, n - (n + 2) / 3, mod) % mod;
            ans = ans + power(oddNum, n, mod);
            ans %= mod;

            System.out.println(ans);
        }
    }

    // x ^ y
    static long power(long x, long y, int mod) {
        if (y == 0) {
            return 1;
        }
        if ((y & 1) == 1) {
            return 1l * x * power(x, y - 1, mod) % mod;
        }
        return power((1l * x * x) % mod, y >> 1, mod);
    }
}

// 奇数 奇数 偶数 奇数 奇数 偶数  （偶数 = x / 3） 
// 奇数 偶数 奇数 奇数 偶数 奇数 奇数 偶数   偶数 =（x + 1） / 3
// 偶数 奇数 奇数 偶数 奇数 奇数 偶数        偶数 = （x + 2) / 3
// 偶数 偶数 偶数 偶数