title: 错位排列 id: 23f96b70-5b7c-46fa-b358-69319154a761 date: 2025-02-07 12:45:29 auther: zengtudor cover: /upload/126925278.jpg excerpt: [SDOI2016] 排列计数题解注意，本文章代码由人类编写但是文章由AI书写原文地址题目大意求有多少种 1 到 n 的排列 a，满足恰好有 m 个位置 i 使得 a_i = i。答案对 permalink: /archives/cuo-wei-pai-lie categories:

cpp tags:
c

[SDOI2016] 排列计数题解

注意，本文章代码由人类编写但是文章由AI书写

原文地址

题目大意

求有多少种 $1$ 到 $n$ 的排列 $a$ ，满足恰好有 $m$ 个位置 $i$ 使得 $a_i = i$ 。答案对 $10^9 + 7$ 取模。

解题思路

我们需要找出恰好 $m$ 个位置固定的排列数。这个问题可以分为两部分：

选择固定点：从 $n$ 个位置中选择 $m$ 个作为固定点，组合数为 $C(n, m)$ 。
错位排列：剩下的 $n - m$ 个位置必须都不在原来的位置上，称为错位排列，记作 $D(n - m)$ 。

总方案数为两者的乘积，即 $C(n, m) \times D(n - m) \mod (10^9 + 7)$ 。

组合数计算

组合数 $C(n, m)$ 可以通过预处理阶乘和阶乘的逆元来快速计算。公式为：

C(n, m) = \frac{n!}{m! \times (n - m)!} \mod p

其中 $p = 10^9 + 7$ 。

错位排列数

错位排列数 $D(k)$ 满足递推关系：

$D(0) = 1$ （空排列视为一个错排）
$D(1) = 0$
当 $k \geq 2$ 时， $D(k) = (k - 1) \times (D(k - 1) + D(k - 2)) \mod p$

预处理

阶乘数组：预处理 $fact[i] = i! \mod p$ 。
阶乘逆元数组：利用费马小定理预处理 $invfact[i] = (i!)^{-1} \mod p$ 。
错位排列数组：预处理 $der[i]$ 表示 $D(i)$ 。

代码实现

预处理阶乘、逆元和错位排列数组后，每个测试用例只需 $O(1)$ 时间计算答案。

边界情况

当 $m > n$ 时，答案为 $0$ 。
当 $n = m$ 时，答案为 $1$ （因为 $D(0) = 1$ ）。

示例代码

#include <iostream>
using namespace std;

typedef long long ll;
const ll maxn = 1e6, p = 1e9 + 7;
ll fact[maxn + 5], invfact[maxn + 5], der[maxn + 5];

ll qpow(ll b, ll e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * b % p;
        b = b * b % p;
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 预处理阶乘
    fact[0] = 1;
    for (ll i = 1; i <= maxn; ++i)
        fact[i] = fact[i - 1] * i % p;

    // 预处理阶乘逆元
    invfact[maxn] = qpow(fact[maxn], p - 2);
    for (ll i = maxn - 1; i >= 0; --i)
        invfact[i] = invfact[i + 1] * (i + 1) % p;

    // 预处理错位排列
    der[0] = 1;
    der[1] = 0;
    for (ll i = 2; i <= maxn; ++i)
        der[i] = (i - 1) * (der[i - 1] + der[i - 2]) % p;

    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m;
        if (m > n) {
            cout << "0\n";
            continue;
        }
        ll C = fact[n] * invfact[m] % p * invfact[n - m] % p;
        cout << der[n - m] * C % p << '\n';
    }
}

复杂度分析

预处理： $O(n)$ ，每个数组的预处理均为线性复杂度。
查询：每次查询 $O(1)$ ，总复杂度 $O(T)$ 。

该算法能够高效处理 $n \leq 10^6$ 和 $T \leq 5 \times 10^5$ 的情况。

[SDOI2016] 排列计数 题解