题解 | 小红的双生排列

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    // 预加载 n!
    static final int MOD = 1_000_000_007;
    static final int MAX = 1_000_000;          // 按需调整
    static final long[] FACT = new long[MAX + 1];

    static {                                   // 类加载时一次性算完
        FACT[0] = 1;
        for (int i = 1; i <= MAX; i++)
            FACT[i] = FACT[i - 1] * i % MOD;
    }

    // O(1) 查询
    public static long factorial(int n) {
        if (n < 0 || n > MAX) throw new IllegalArgumentException();
        return FACT[n];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();

        long res = 0;

        // 如果n 为偶数
        if (n % 2 == 0) {
            // 奇数集合与偶数集合的数量是一样的  n/2
            int m = n / 2;
            long mf = factorial(m);
            // 奇数集合 有 n/2 !
            // 偶数集合 有 n/2 !
            // 但是可以交换两个集合排列的位置 奇数下标 0 2 4 偶数下标 1 3 5
            // 偶数下标 0 2 4 奇数下标 1 3 5
            res = mf * mf * 2 % MOD;

        } else {
            //n 为奇数
            // 奇数集合数量为 n/2 +1
            // 偶数集合数量为 n/2
            long js = factorial(n / 2 + 1);
            long os = factorial(n / 2);
            // 奇数只能排 0 2 4
            res = js * os % MOD;

        }
        System.out.println(res);
    }
}