小欧的排列计算

2026/10/24约 1597 字大约 5 分钟

小欧的排列计算

OPPO 笔试真题 · 2023 秋招 · 算法岗
判题请到牛客原题提交。

题目描述

定义一个排列为“好排列”，当且仅当所有相邻两个数的乘积均为偶数。

小欧想知道，长度 $n$ 的好排列一共有多少种？由于该数可能过大，请对 $10^9+7$ 取模。

输入格式

一个正整数 $n$ 。

$2 \le n \le 10^5$

输出格式

好排列的数量。

示例

示例 1

输入：

输出：

说明：

好排列有[1,2]和[2,1]。

示例 2

输入：

输出：

说明：

好排列有[1,2,3]和[3,2,1]。

解题思路

第一步：把「乘积是偶数」翻译成结构条件

两个数相乘是偶数，当且仅当至少有一个是偶数。反过来，乘积是奇数当且仅当两个都是奇数。

所以「所有相邻两数乘积都是偶数」等价于一条非常干净的限制：

排列里不能出现两个相邻的奇数。

偶数的位置完全自由，它们之间随便相邻都没关系 —— 偶数乘偶数、偶数乘奇数都是偶数。

第二步：数一数奇数和偶数各有多少个

$1 \sim n$ 中，偶数有 $e = \lfloor n/2 \rfloor$ 个，奇数有 $o = n - e$ 个。

如果奇数比「偶数个数 + 1」还多，那么无论怎么摆，必然有两个奇数挨在一起（鸽笼原理），
此时答案是 0。对 $1 \sim n$ 这个集合来说， $o$ 最多比 $e$ 大 1，所以这个分支不会触发；
留它在代码里是为了让逻辑对「任意集合」也成立。

第三步：插空法计数

既然奇数不能相邻，就先把偶数排好，再把奇数「插」到空隙里：

排偶数： $e$ 个偶数随便排，有 $e!$ 种；
数空隙： $e$ 个偶数排成一排后，前面、后面、以及每两个相邻偶数之间都是空隙，一共 $e+1$ 个（两端也算）；
选空隙：从 $e+1$ 个空隙里挑 $o$ 个，每个空隙最多放一个奇数，有 $\binom{e+1}{o}$ 种；
排奇数：放进空隙的 $o$ 个奇数内部可以任意换位置，有 $o!$ 种。

三步互相独立，乘起来就是答案：

e! \cdot \binom{e+1}{o} \cdot o! \pmod{10^9+7}

完整代码实现

import sys
from math import comb

MOD = 10 ** 9 + 7


def solve() -> None:
    """插空法计数：偶数先排，奇数插进空隙"""
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])

    even = n // 2          # 偶数的个数
    odd = n - even         # 奇数的个数

    # 奇数太多，怎么排都会有两个奇数相邻
    if odd > even + 1:
        sys.stdout.write("0\n")
        return

    # 预处理阶乘（只需要到 even+1）
    fact = [1] * (even + 2)
    for i in range(1, even + 2):
        fact[i] = fact[i - 1] * i % MOD

    # 偶数排列 × 选空隙 × 奇数排列
    ans = fact[even] * (comb(even + 1, odd) % MOD) % MOD * fact[odd] % MOD
    sys.stdout.write(str(ans) + "\n")


if __name__ == "__main__":
    solve()

示例推演

示例 1：`n = 2`

数字是 $\{1, 2\}$ ， $e = 1$ （偶数 2）， $o = 1$ （奇数 1）。

步骤	计算	结果
排偶数	$1!$	1（只有 `2`）
空隙	`_2_` 共 2 个	选 1 个放奇数
选空隙	$\binom{2}{1}$	2
排奇数	$1!$	1
合计	$1 \times 2 \times 1$	2

对应 [2,1] 和 [1,2]，与题面一致。

示例 2：`n = 3`

数字是 $\{1, 2, 3\}$ ， $e = 1$ （偶数 2）， $o = 2$ （奇数 1、3）。

步骤	计算	结果
排偶数	$1!$	1（只有 `2`）
空隙	`_2_` 共 2 个	必须两个都放
选空隙	$\binom{2}{2}$	1
排奇数	$2!$	2
合计	$1 \times 1 \times 2$	2

对应 [1,2,3] 和 [3,2,1]，与题面一致。

补充例子：`n = 4`

$e = 2$ （2、4）， $o = 2$ （1、3）。

排偶数： $2! = 2$ 种（2 4、4 2）；
空隙有 3 个，例如 _2_4_，从中选 2 个： $\binom{3}{2} = 3$ 种；
两个奇数内部： $2! = 2$ 种。

合计 $2 \times 3 \times 2 = 12$ 。程序对 $n=4$ 输出 12，与暴力枚举全排列的结果一致。

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举全排列逐一检查	O(n! · n)	O(n)	n 稍大就不可行
插空法 + 阶乘	O(n)	O(n)	推荐；`math.comb` 内部也是精确计算
插空法 + 递推求组合数	O(n)	O(n)	C++ 里常用阶乘 + 逆元实现

易错点总结

1. 只判「奇数不能相邻」，却把空隙数算成 e − 1

$e$ 个偶数排好后空隙是 $e+1$ 个 —— 两端也要算。少算两端会漏掉
「奇数全部放在最前或最后」这类排列。

2. 忘记乘 $o!$

奇数不是相同的元素：选好哪几个空隙之后，放进去的 $o$ 个奇数还能互换位置。

3. 组合数没取模

$\binom{e+1}{o}$ 本身可能非常大，必须一起取模；Python 里可以先用 math.comb
算出精确值再 % MOD，C++ 里要用「阶乘 + 费马小定理求逆元」。

4. 把「不能相邻」理解成「必须一奇一偶交替」

交替排列只是其中一部分（当 $o = e$ 或 $o = e+1$ 时的一种极端情况），
本题允许两个偶数相邻，所以答案是交替排列数的好几倍。

5. 边界 n 很小时的特判

$n = 2$ 时 $e = 1, o = 1$ ，公式给出 2，不需要额外分支；只要保证阶乘数组开到
$e+1$ 就不会越界。

扩展思考

如果要求相邻两数奇偶性一定不同（完全交替）：答案只有 $e! \cdot o!$ 的两种摆放顺序，
即 $|e - o| \le 1$ 时非零。
如果要求相邻乘积是 3 的倍数：条件变成「不能有相邻两个都不是 3 的倍数」，
插空的对象从「奇数」换成「非 3 的倍数」，思路完全一样。
如果要求整个排列的乘积是偶数：那就只要「至少有一个偶数」，答案 $n! - o!$ 。
可以看出「局部条件」和「全局条件」的计数方法差别很大。
插空法是排列组合里的通用技巧：先把「有冲突的元素」拿出去，排好其余元素，
再把冲突元素塞进空隙。相邻不同色、相邻不相等一类的问题都可以这样处理。

相关题目

小欧的排列交换