Java 实现与详细解析

一、问题分析

核心条件

双生排列要求任意相邻两项之和为奇数，根据数学规律：

奇数 + 偶数 = 奇数，奇数 + 奇数 / 偶数 + 偶数 = 偶数

因此：排列必须严格奇偶交替排列。

排列的奇偶数量规律

1~n 中：

• 偶数个数：even = n/2
• 奇数个数：odd = (n+1)/2

合法排列的唯一条件

要实现严格奇偶交替，奇数和偶数的数量只能相差 0 或 1：

1. n 为偶数：奇数个数 = 偶数个数 = n/2 → 合法
2. n 为奇数：奇数个数 = 偶数个数 + 1 → 合法
3. 不存在其他情况，因此所有 n≥2 都满足数量条件

排列组合计算

1. n 为偶数：两种排列模式：奇偶奇偶... 或 偶奇偶奇...
1. 奇数全排列：(n/2)!，
2. 偶数全排列：(n/2)!
3. 总数量 = 2 * (n/2)! * (n/2)!
2. n 为奇数：只能是 奇偶奇偶...奇（奇数必须开头和结尾）
1. 奇数全排列：((n+1)/2)!，
2. 偶数全排列：(n/2)!
3. 总数量 = ((n+1)/2)! * (n/2)!

二、解题思路

1. 预处理阶乘数组：因为 n 最大 1e5，提前计算1! ~ 1e5!对1e9+7取模的值
2. 根据 n 的奇偶性，套用公式计算结果
3. 输出结果取模

三、代码

import java.util.*;
import java.lang.Long;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 取模常量
    public static final int MOD = 1000000007;
    // 最大n为1e5，预处理阶乘
    public static final int MAX = 100005;
    // 阶乘数组，fact[i] = i! % MOD
    public static long[] fact = new long[MAX];

    // 预处理阶乘
    public static void preProcess() {
        fact[0] = 1;
        for (int i = 1; i < MAX; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { 
            int n = in.nextInt();
            // 先预处理阶乘
            preProcess();
            long ans;

            if (n % 2 == 0) {
                // 偶数情况：2 * (n/2)! * (n/2)!
                int m = n / 2;
                ans = 2 * fact[m] % MOD;
                ans = ans * fact[m] % MOD;
            } else {
                // 奇数情况：((n+1)/2)! * (n/2)!
                int odd = (n + 1) / 2;
                int even = n / 2;
                ans = fact[odd] * fact[even] % MOD;
            }

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