lasing - 题解

标签与难度

标签: 组合数学, 排列, 错排问题, 容斥原理, 逆元, 数论难度: 1600

题目大意喵~

ฅ( • ﻌ • )ฅ 各位看官请听好喵~ 这道题是说，给定一个数字 $n$ ，我们要找出在所有长度为 $n$ 的排列 $p$ 中，有多少个排列满足至少有 4 个位置 $i$ 上的数 $p_i$ 不等于 $i$ 。

换句话说，我们要统计有多少种排列，使得“不在自己位置上”的元素至少有 4 个。

举个例子，如果 $n=4$ ，排列 [2, 1, 4, 3] 就是一个满足条件的排列，因为 $p_1=2 \ne 1, p_2=1 \ne 2, p_3=4 \ne 3, p_4=3 \ne 4$ ，所有 4 个元素都不在自己的位置上，满足“至少有4个”的要求。

最后的结果需要对 998244353 取模，可别忘了哦！

解题思路分析

面对“至少”这种字眼，直接去数“恰好有4个不在位”、“恰好有5个不在位”……直到“恰好有n个不在位”的情况，然后加起来，虽然是可行的，但可能会有点小麻烦呢，喵~

这时候，我的小脑袋瓜里就会闪过一个绝妙的想法：正难则反！

直接数“至少4个不在位”有点复杂，那我们不如反过来数它的对立面：“少于4个不在位”的排列有多少种！然后用总的排列数减去这部分，不就得到答案了嘛？嘿嘿，是不是很机智？

“少于4个不在位”的排列，就意味着有 0、1、2、或者 3 个元素不在自己的位置上。我们来逐一分析这些情况，喵~

一个元素 $p_i$ 在自己的位置上，我们称之为不动点（Fixed Point）。那么“不在自己位置上”的元素就是非不动点。

总的排列数: 对于长度为 $n$ 的序列，总共有 $n!$ 种不同的排列。
对立面分析: 我们要减去非不动点个数为 0, 1, 2, 3 的情况。
- 情况一：0 个非不动点 这意味着所有元素都在自己的位置上，即 $p_i = i$ 对所有的 $i$ 都成立。这不就是传说中的单位排列 [1, 2, 3, ..., n] 嘛！这种情况只有 1 种。
- 情况二：1 个非不动点 这种情况可能吗？喵~ 让我们想一想。如果有 $n-1$ 个元素都在自己的位置上，比如除了第 $k$ 个元素，其他都满足 $p_i=i$ 。那么剩下的元素值就只有 $k$ 了，它能去哪儿呢？只能去剩下的位置 $k$ 呀！所以 $p_k$ 也必须等于 $k$ 。这样一来，就变成 0 个非不动点了。所以，恰好有 1 个非不动点的情况是不存在的！数量为 0 种。
- 情况三：2 个非不动点 这意味着有 $n-2$ 个不动点。我们分两步来数：
  1. 首先，从 $n$ 个位置中选出 2 个位置来当“非不动点”。有多少种选法呢？当然是组合数 $C(n, 2)$ 啦！
  2. 假设我们选了位置 $i$ 和 $j$ 。那么元素 $i$ 和 $j$ 就必须放在这两个位置上，并且都不能在自己的老家。也就是说 $p_i \ne i$ 且 $p_j \ne j$ 。唯一的办法就是让它们交换位置： $p_i = j, p_j = i$ 。这种把一组元素全部安排到非自己位置上的排列，我们称之为错排（Derangement）。2个元素的错排数 $D_2 = 1$ 。所以，这种情况的总数是 $C(n, 2) \times D_2 = C(n, 2) \times 1 = C(n, 2)$ 种。
- 情况四：3 个非不动点 和上面的思路一样，喵~
  1. 从 $n$ 个位置中选出 3 个位置，有 $C(n, 3)$ 种选法。
  2. 假设我们选了位置 $i, j, k$ 。元素 $i, j, k$ 就要在这三个位置上进行一次“全员错排”。3个元素的错排数 $D_3 = 2$ 。（比如对于元素 1,2,3，它们的错排是 [2, 3, 1] 和 [3, 1, 2]）所以，这种情况的总数是 $C(n, 3) \times D_3 = C(n, 3) \times 2$ 种。

好啦，我们已经把所有“坏”情况都数清楚了。总共有 $1 + 0 + C(n, 2) + 2 \times C(n, 3)$ 种我们不想要的排列。

那么，最终的答案就是：

\text{答案} = n! - (1 + C(n, 2) + 2 \times C(n, 3))

剩下的工作就是计算 $n!$ , $C(n, 2)$ 和 $C(n, 3)$ 在模 998244353 意义下的值啦。

$C(n, 2) = \frac{n(n-1)}{2} = n \times (n-1) \times 2^{-1} \pmod{998244353}$
$C(n, 3) = \frac{n(n-1)(n-2)}{6} = n \times (n-1) \times (n-2) \times 6^{-1} \pmod{998244353}$

这里的 $2^{-1}$ 和 $6^{-1}$ 是模逆元，可以用快速幂求得。

最后，别忘了处理 $n<4$ 的情况。如果 $n<4$ ，那么非不动点的个数也必然小于4，所以答案就是0。

代码实现

下面是我根据这个思路精心编写的代码，注释超详细的哦，希望能帮到你，喵~

cpp

#include <iostream>

// 定义一个我喜欢的名字作为模数
const long long MOD = 998244353;

// 快速幂函数，用来计算 a^b % MOD
// 也是求逆元的好帮手哦！
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元函数，a^{-1} mod m = a^{m-2} mod m (根据费马小定理)
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    // 为了让输入输出快一点，像猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n;
    std::cin >> n;

    // 如果 n < 4，不可能有至少4个非不动点，直接输出0
    if (n < 4) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // --- 开始计算公式的各个部分 ---

    // 1. 计算 n! mod MOD
    long long factorial_n = 1;
    for (long long i = 1; i <= n; ++i) {
        factorial_n = (factorial_n * i) % MOD;
    }

    // 2. 计算 C(n, 2) mod MOD
    // C(n, 2) = n * (n - 1) / 2
    long long inv2 = modInverse(2);
    long long comb_n_2 = (n % MOD * ((n - 1) % MOD)) % MOD;
    comb_n_2 = (comb_n_2 * inv2) % MOD;

    // 3. 计算 C(n, 3) mod MOD
    // C(n, 3) = n * (n - 1) * (n - 2) / 6
    long long inv6 = modInverse(6);
    long long comb_n_3 = (n % MOD * ((n - 1) % MOD)) % MOD;
    comb_n_3 = (comb_n_3 * ((n - 2) % MOD)) % MOD;
    comb_n_3 = (comb_n_3 * inv6) % MOD;

    // --- 整合答案 ---

    // 计算不满足条件的排列总数：1 (0个非不动点) + C(n, 2) (2个) + 2*C(n, 3) (3个)
    long long unwanted_perms = 1;
    unwanted_perms = (unwanted_perms + comb_n_2) % MOD;
    unwanted_perms = (unwanted_perms + (2 * comb_n_3) % MOD) % MOD;

    // 总排列数减去不想要的排列数
    // (a - b) % MOD = (a - b + MOD) % MOD，防止出现负数
    long long ans = (factorial_n - unwanted_perms + MOD) % MOD;

    std::cout << ans << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(n)$ 我们的代码中，最耗时的部分是计算 $n!$ 的那个循环，它执行了 $n$ 次。计算模逆元和组合数都是常数级别的操作（快速幂的时间复杂度是 $O(\log MOD)$ ，但因为底数是固定的2和6，可以看作常数时间）。所以，总的时间复杂度由计算阶乘主导，为 $O(n)$ ，非常高效，喵~
空间复杂度: $O(1)$ 我们只用了几个变量来存储中间结果（factorial_n, comb_n_2, comb_n_3 等），没有使用与 $n$ 大小相关的额外数组。所以空间复杂度是 $O(1)$ ，非常节省内存！

知识点总结

这道题就像一盘精致的猫饭，融合了多种美味的知识点，呐：

组合数学 (Combinatorics): 整个问题都建立在排列和组合的计数之上。
补集思想 (Complementary Counting): “至少”问题的经典克星！当正面强攻困难时，从反面入手往往能柳暗花明。
错排问题 (Derangement): 虽然我们只用到了 $D_2$ 和 $D_3$ 的值，但理解错排的概念（一个元素都不能在自己原来的位置上）是解决问题的关键。
模运算 (Modular Arithmetic): 在处理大数计数问题时，模运算是必备技能。尤其要注意减法可能产生负数，需要 (a - b + MOD) % MOD 来保证结果非负。
模逆元 (Modular Inverse): 在模意义下做除法，就需要用到乘法逆元。费马小定理是求模逆元的有力工具，当模数是质数时， $a$ 的逆元就是 $a^{MOD-2}$ 。

希望这篇题解能让你对这些知识点有更深的理解，喵~ 如果还有问题，随时可以再来问我哦！( ´ ▽ ` )ﾉ

lasing - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​