喵~ 主人，今天我们来看一道关于排列组合的有趣问题哦！这道题叫做 "Almost Identity Permutations"，听起来是不是有点小傲娇？嘿嘿，别担心，只要跟着我的思路，我们就能轻松搞定它啦！

题目大意

题目是这样哒：首先，我们要知道什么是排列 (Permutation)。一个大小为 n 的排列 p，就是把 1 到 n 这 n 个数字重新排个队，每个数字都必须出现一次，不能多也不能少哦。

然后呢，题目定义了一种叫做**“几乎是单位排列” (Almost Identity Permutation)** 的东西。如果一个排列 p 至少有 n-k 个位置 i，满足 p[i] = i，那它就是“几乎是单位排列”啦。p[i] = i 的位置我们叫它**“不动点”**，就是说这个位置上的数字没有动过。

所以，“至少有 n-k 个不动点”，反过来说，就是**“最多有 k 个位置上的数字动了”，对不对呀？这些动了位置的点，我们就叫它们“错位点”**好了。

我们的任务就是，给定 n 和 k，计算出到底有多少种这样的“几乎是单位排列”呢？

题解方法

嘻嘻，这个问题可以分解一下哦。既然是要求“最多”有 k 个错位点的排列数量，那我们就可以把有 0 个错位点、1 个错位点、2 个错位点...一直到 k 个错位点的排列数量全部加起来，就是最终答案啦！

那么，对于一个固定的数字 m (m <= k)，我们要怎么计算恰好有 m 个错位点的排列数量呢？

这可以分两步走，就像猫猫捕食一样，要先锁定目标，再发起攻击！

1. 第一步：选出哪些位置要错位。 我们有 n 个位置，要从里面选出 m 个来当错位点。剩下的 n-m 个位置就是不动点啦（p[i] = i）。从 n 个里面选 m 个，有多少种选法呢？这就是组合数 C(n, m) 啦！

2. 第二步：让选出的 m 个元素全部错位。 假设我们选了 m 个位置 i₁, i₂, ..., iₘ。那么在这些位置上的排列，必须满足 p[iⱼ] ≠ iⱼ 对所有的 j 都成立。也就是说，这 m 个元素要进行一个“完全错位”的排列。这种特殊的排列就叫做 错位排列 (Derangement)，它的数量我们记作 Dₘ。

所以，恰好有 m 个错位点的排列数量就是： C(n, m) × Dₘ

我们的总答案就是把 m 从 0 到 k 的所有情况加起来： 总数 = Σ (从 m=0 到 k) [ C(n, m) × Dₘ ]

因为题目里 k 的值非常小 (1 ≤ k ≤ 4)，我们根本不需要写循环，只要根据 k 的值，把对应的情况加起来就好啦，是不是很简单呀？

题解

好啦，我们来动手算一算吧！首先，我们需要知道几个小的错位排列数 Dₘ：

• D₀ = 1：0个元素错排，只有一种情况（就是空集本身），这是个数学定义，记住就好喵~
• D₁ = 0：1个元素，怎么都放不对自己的位置？不可能的啦！
• D₂ = 1：2个元素 {1, 2}，只有一种错排方式：{2, 1}。
• D₃ = 2：3个元素 {1, 2, 3}，有两种错排方式：{2, 3, 1} 和 {3, 1, 2}。
• D₄ = 9：4个元素，有9种错排方式。

现在，我们根据 k 的值来累加答案：

• 当 k ≥ 0 时（题目保证 k ≥ 1），我们计算 m=0 的情况：

  • 有 0 个错位点，也就是所有 p[i] = i，这就是单位排列本身。
  • 数量 = C(n, 0) × D₀ = 1 × 1 = 1。
  • 所以，我们的答案 ans 先加上 1。

• 当 k ≥ 1 时，我们考虑 m=1 的情况：

  • 有 1 个错位点。
  • 数量 = C(n, 1) × D₁ = n × 0 = 0。
  • 这种情况是不可能存在的，所以对答案没有贡献。

• 当 k ≥ 2 时，我们计算 m=2 的情况：

  • 有 2 个错位点。
  • 数量 = C(n, 2) × D₂ = (n * (n - 1) / 2) × 1。
  • 如果 k ≥ 2，就把这个数加到 ans 上。

• 当 k ≥ 3 时，我们计算 m=3 的情况：

  • 有 3 个错位点。
  • 数量 = C(n, 3) × D₃ = (n * (n - 1) * (n - 2) / 6) × 2。
  • 如果 k ≥ 3，就把这个数加到 ans 上。

• 当 k ≥ 4 时，我们计算 m=4 的情况：

  • 有 4 个错位点。
  • 数量 = C(n, 4) × D₄ = (n * (n - 1) * (n - 2) * (n - 3) / 24) × 9。
  • 如果 k = 4，就把这个数加到 ans 上。

把这些加起来就是最终的答案啦！下面就是实现这个思路的代码，超级直白哦！

#include <iostream>

int main() {
    // 提高一下输入输出效率，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n;
    int k;
    std::cin >> n >> k;

    long long ans = 0;

    // 题目要求的是“至少 n-k 个不动点”，等价于“至多 k 个错位点”。
    // 我们把错位点个数为 0, 1, ..., k 的情况加起来。
    // 错位点个数为 m 的排列数 = C(n, m) * D_m
    // 其中 C(n, m) 是组合数，D_m 是 m 个元素的错位排列数。
    
    // D_0 = 1, D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9

    // 情况一：m = 0 个错位点 (k >= 0 总成立, 题目保证 k>=1)
    // 数量 = C(n, 0) * D_0 = 1 * 1 = 1
    ans += 1;

    // 情况二：m = 1 个错位点
    // 数量 = C(n, 1) * D_1 = n * 0 = 0
    // 对答案无贡献

    // 情况三：m = 2 个错位点 (当 k >= 2 时)
    // 数量 = C(n, 2) * D_2 = (n * (n - 1) / 2) * 1
    if (k >= 2) {
        ans += (n * (n - 1)) / 2;
    }

    // 情况四：m = 3 个错位点 (当 k >= 3 时)
    // 数量 = C(n, 3) * D_3 = (n * (n - 1) * (n - 2) / 6) * 2
    if (k >= 3) {
        ans += (n * (n - 1) * (n - 2) / 6) * 2;
    }

    // 情况五：m = 4 个错位点 (当 k >= 4 时)
    // 数量 = C(n, 4) * D_4 = (n * (n - 1) * (n - 2) * (n - 3) / 24) * 9
    if (k >= 4) {
        ans += (n * (n - 1) * (n - 2) * (n - 3) / 24) * 9;
    }

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

    return 0;
}

知识点介绍

最后，我们来复习一下这道题里用到的数学小知识吧，主人要认真听哦！

• 排列 (Permutation):

  • 就是从 n 个不同元素中，取出全部 n 个元素，按一定的顺序排成一列。比如 {1, 2, 3} 的全排列有 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 这 6 种。

• 组合 (Combination):

  • 从 n 个不同元素中，取出 m 个元素并成一组，不考虑顺序。记作 C(n, m) 或 Cₙᵐ。
  • 计算公式是：C(n, m) = n! / (m! * (n-m)!)。在代码里我们通常直接计算 n * (n-1) * ... * (n-m+1) / m! 来避免阶乘过大。

• 错位排列 (Derangement):

  • 这是一个非常经典又好玩的组合数学问题！
  • 定义： 一个 n 个元素的排列，如果所有元素都不在自己原来的位置上，那么这个排列就是一个 n 元错位排列。
  • 递推公式： 设 Dₙ 为 n 个元素的错位排列数，那么有 Dₙ = (n-1) * (Dₙ₋₁ + Dₙ₋₂) (n ≥ 2)。这个公式的理解方式有点小复杂，主人有兴趣可以自己研究一下哦，可以想象第 n 个元素放到了 k 的位置，然后分情况讨论第 k 个元素放哪~
  • 前几项的值：
    • D₀ = 1
    • D₁ = 0
    • D₂ = 1
    • D₃ = 2
    • D₄ = 9
    • D₅ = 44
  • 在这道题里，我们只需要用到 D₀ 到 D₄，所以直接记住它们的值就可以啦！

好啦，今天的题解就到这里结束了喵~ 主人有没有觉得豁然开朗呢？组合数学的世界是不是很有趣呀？下次再见啦，喵~