题解 | 小欧的排列计算

题目链接：牛客Link

思路

偶数 × 任意数 = 偶数
奇数 × 奇数 = 奇数

所以题目排列中不能出现两个相邻的奇数

在 $1$ ~ $n$ 中：

奇数个数 $o = \left\lceil \frac{n}{2} \right\rceil = \frac{n+1}{2}$
偶数个数 $e = \left\lfloor \frac{n}{2} \right\rfloor = \frac{n}{2}$

插空法计数

相邻两个数乘积为偶数 ⇔ 不能有两个奇数相邻。

先排列偶数
- 偶数共有 $e$ 个，任意顺序合法，方案数： $e!$
插入奇数
- 偶数排好后产生 $e+1$ 个空位，为避免奇数相邻，每个空位最多放 $1$ 个奇数，从中选 $o$ 个空位： $\binom{e+1}{o}$
排列奇数
- 奇数共有 $o$ 个，任意排列，方案数： $o!$

所以：

\text{答案} = e! \times \binom{e+1}{o} \times o! \pmod{10^9+7}

知识拓展：逆元

逆元的概念

在模 $m$ 下， $b$ 是 $a$ 的逆元，当且仅当：

$a \cdot b \equiv 1 \pmod{m}$

逆元存在的条件是：

$\gcd(a, m) = 1$

例子 $a = 3, m = 7$ ：

$3 \cdot b \equiv 1 \pmod{7} \implies b = 5$

费马小定理（模质数）

定理内容

设 $p$ 是质数，且 $\gcd(a,p)=1$ ，则：

$a^{p-1} \equiv 1 \pmod{p}$

等价地：

$a \cdot a^{p-2} \equiv 1 \pmod{p}$

逆元公式

$a^{-1} \equiv a^{p-2} \pmod{p}$

例子 $a=3, p=7$ ：

$3^{-1} \equiv 3^{7-2} = 3^5 \pmod{7}$

计算：

$3^2 \equiv 9 \equiv 2 \pmod{7} \\ 3^4 \equiv 2^2 \equiv 4 \pmod{7}\\ 3^5 \equiv 3^4 \cdot 3 \equiv 4 \cdot 3 \equiv 12 \equiv 5 \pmod{7}$

扩展欧几里得法（一般模数）

求 $x$ ，使得：

$a \cdot x \equiv 1 \pmod{m} \quad \Leftrightarrow \quad a x + m y = \gcd(a,m)$

如果 $\gcd(a,m) = 1$ ，则 $x$ 即为逆元：

$a^{-1} \equiv x \pmod{m}$

费马小定理法（模质数 $p$ ）：
// a^b mod p
long long mod_pow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// a^-1 mod p
long long mod_inverse(long long a, long long p) {
    return mod_pow(a, p - 2, p); // 对应公式 a^(p-2) ≡ a^-1 (mod p)
}
扩展欧几里得法（一般模数 $m$ ）：
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

// a^-1 mod m
long long mod_inverse_general(long long a, long long m) {
    long long x, y;
    long long g = exgcd(a, m, x, y);
    if (g != 1) return -1; // 无逆元
    return (x % m + m) % m; // 确保正数
}

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long mod_pow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;

    int odd = (n + 1) / 2;
    int even = n / 2;

    // 预处理阶乘和逆阶乘
    vector<long long> fact(n + 2, 1), invfact(n + 2, 1);

    for (int i = 1; i <= n + 1; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    // 计算逆阶乘
    invfact[n + 1] = mod_pow(fact[n + 1], MOD - 2, MOD);
    for (int i = n + 1; i > 0; --i) {
        invfact[i - 1] = invfact[i] * i % MOD;
    }

    // 组合数 C(a, b)
    auto C = [&](int a, int b) -> long long {
        if (b < 0 || b > a) return 0;
        return fact[a] * invfact[b] % MOD * invfact[a - b] % MOD;
    };

    // 计算答案
    long long ans = fact[even] * C(even + 1, odd) % MOD;
    ans = ans * fact[odd] % MOD;

    cout << ans << endl;

    return 0;
}

Python

MOD = 10**9 + 7

n = int(input().strip())

# 计算奇偶数个数
odd = (n + 1) // 2
even = n // 2

# 预处理阶乘和逆元
fact = [1] * (n + 2)
invfact = [1] * (n + 2)

for i in range(1, n + 2):
    fact[i] = fact[i - 1] * i % MOD

# 计算逆阶乘
invfact[n + 1] = pow(fact[n + 1], MOD - 2, MOD)
for i in range(n + 1, 0, -1):
    invfact[i - 1] = invfact[i] * i % MOD

# 组合数 C(a, b)
def C(a, b):
    if b < 0 or b > a:
        return 0
    return fact[a] * invfact[b] % MOD * invfact[a - b] % MOD

# 总数 = e! * C(e+1, o) * o!
ans = fact[even] * C(even + 1, odd) % MOD
ans = ans * fact[odd] % MOD

print(ans)

优化

如果你能想到化简公式和本题中恒有 $o = \left\lceil \frac{n}{2} \right\rceil, \quad e = \left\lfloor \frac{n}{2} \right\rfloor$ ，即 $o = e$ 或 $o = e+1$

原公式：

\text{答案} = e! \times \binom{e+1}{o} \times o! \pmod{10^9+7}

尝试化简

组合数定义为：

\binom{e+1}{o} = \frac{(e+1)!}{o! , (e+1-o)!}

代入原公式：

\text{答案} = e! \times \frac{(e+1)!}{o! , (e+1-o)!} \times o!

$o!$ 可以与分母抵消：

\text{答案} = e! \times \frac{(e+1)!}{(e+1-o)!}

本题中： $o = \lceil n/2 \rceil, \quad e = \lfloor n/2 \rfloor$

所以：

当 $n$ 偶数时， $o = e$

(e+1-o)! = (e+1-e)! = 1! \\ \\ \text{答案} = e! \times (e+1)!

当 $n$ 奇数时， $o = e+1$

(e+1-o)! = (e+1-(e+1))! = 0! = 1 \\ \\ \text{答案} = e! \times (e+1)!

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;

    int e = n / 2;

    // 预处理阶乘
    vector<long long> fact(n + 2, 1);
    for (int i = 1; i <= n + 1; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    // 计算答案
    long long ans = fact[e] * fact[e + 1] % MOD;

    cout << ans << endl;
    return 0;
}

Python

MOD = 10**9 + 7

n = int(input().strip())

# 计算偶数个数 e
e = n // 2

# 计算阶乘
fact = [1] * (n + 2)
for i in range(1, n + 2):
    fact[i] = fact[i-1] * i % MOD

# 答案 = e! * (e+1)! % MOD
ans = fact[e] * fact[e+1] % MOD

print(ans)