组合数学与错位排列在算法竞赛中的应用

1. 项目背景与问题解析

这道题目来自山东省队选拔赛2016年的压轴题，考察的是排列组合与错位排列的综合应用能力。题目要求我们计算在1到n的排列中，恰好有m个数字保持原位的排列数。这类问题在信息学竞赛中属于中等偏上难度，需要选手对组合数学有扎实的理解。

我第一次遇到这个问题时，花了整整一个下午才完全理解题意。关键在于"恰好m个数字在原位"这个条件——这意味着剩下的n-m个数字必须全部不在原位，也就是所谓的"错位排列"。

2. 数学原理与公式推导

2.1 组合数学基础

要解决这个问题，我们需要两个核心数学概念：

1. 组合数C(n,m)：从n个元素中选出m个的组合数
2. 错位排列数D(k)：k个元素的排列中，所有元素都不在原来位置的排列数

题目所求的答案可以表示为：C(n,m) × D(n-m)

2.2 错位排列的递推公式

错位排列数D(n)有以下几种计算方法：

1. 递推公式：D(n) = (n-1)×(D(n-1)+D(n-2))
2. 通项公式：D(n) = n! × Σ(-1)^k / k! (k从0到n)

在实际编程实现中，递推公式更适合，因为：

• 时间复杂度O(n)可接受
• 避免了阶乘计算的精度问题
• 便于预处理所有可能的n值

3. 算法设计与实现

3.1 预处理阶乘和逆元

由于题目要求对1e9+7取模，我们需要预处理阶乘和逆元数组：

cpp复制const int MOD = 1e9+7;
const int MAXN = 1e6;

long long fact[MAXN+5], inv[MAXN+5], D[MAXN+5];

void precompute() {
    // 阶乘和逆元预处理
    fact[0] = inv[0] = 1;
    for(int i=1; i<=MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = pow_mod(fact[i], MOD-2, MOD);
    }
    
    // 错位排列预处理
    D[0] = 1; D[1] = 0;
    for(int i=2; i<=MAXN; i++) {
        D[i] =