题目描述

将 $n$ 封信件的信和信封全部打乱之后，至少有 $n-k$ 封信装在了原来的信封里的情况有多少？

输入样例

5 4

输出样例

76

组合数学

至少 $n-k$ 封信装对相当于至多 $k$ 封信装错

设 $f[i]$ 为 $i$ 封信全部装错的方案数，枚举有 $i$ 封信装错
恰有 $i$ 封信装错的方案数为 $C_n^i \cdot f[i]$

结果为 $\sum_{i = 0}^{k} C_n^i \cdot f[i]$

错排公式

考虑有一个 $i$ 个元素的排列，排列中的每个元素都不在自己原来的位置上，这样的排列被称为一个错排。

上文中的 $f[i]$ 则为 $i$ 个元素的错排的方案数

• 一个常用的递推式：
  $f[0] = f[2] = 1$
  当 $i \geq 3$ 时 $f[i] = (i - 1)(f[i - 2] + f[i - 1])$

• 递推式的一种解释：
  第一步，把第 $i$ 个元素放在某一个位置，比如位置 $k$，一共有 $i-1$ 种方法；
  第二步，放编号为 $k$ 的元素，这时有两种情况：1.它放到位置 $i$ ，那么，对于剩下的 $i - 1$ 个元素，由于第 $k$ 个元素放到了位置 $i$ ，剩下 $i-2$ 个元素就有 $f[i-2]$ 种方法；2.第 $k $ 个元素不把它放到位置 $i$，这时，对于这 $i-1$ 个元素，有 $f[i - 1]$ 种方法。

参考资料

错排公式_百度百科

C++ 代码

#include<cstdio>

typedef long long LL;

const int N = 1010;

int f[N];
LL C(int a, int b)
{
    LL up = 1, down = 1;
    for(int i = a, j = b; j; i --, j --)
        up *= i, down *= j;
    return up / down;
}

int main()
{
    f[0] = f[2] = 1;
    for(int i = 3; i <= 4; i ++)  f[i] = (i - 1) * (f[i - 1] + f[i - 2]);

    int n, k;
    scanf("%d%d", &n, &k);

    LL res = 0;
    for(int i = 0; i <= k; i ++)
        res += C(n, i) * f[i];
    printf("%lld\n", res);
    return 0;
}