CF 888D Almost Identity Permutations 题解

题目大意

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

解题思路

一看题意觉得不难，就是计算不同的排列种类。

后来发现。。

我不会算啊。

其实因为数据不大，所以可以手推有多少种差排方式。

但是为了以后留下知识漏洞，这里补一下差排公式。

设$D(i)$为$i$个数的差排种类数量，$D(1)=0$,$D(2) = 1$。
$$
D(i)=(n-1)*(D(n-1)+D(n-2))
$$
推导过程由此去。

知道错排公式就很简单了。

有1个信封错排时，答案为$1$。

有2个信封错排时，答案为$1*C_n^2$。

有3个信封错排时，答案为$2*C_n^3$。

有4个信封错排时，答案为$9*C_n^4$。

因为是至少$n-k$个，所以累加即可。

完整代码

#include <iostream>
using namespace std;

int main() {
	long long n, k;
	cin >> n >> k;
	long long ans;
	if (k == 1) {
		ans = 1;
	}
	if (k == 2) {
		ans = 1 + (n * (n - 1)) / 2;
	}
	if (k == 3) {
		ans = 1 + (n * (n - 1)) / 2 + (n * (n - 1) * (n - 2)) / 3;
	}
	if (k == 4) {
		ans = 1 + (n * (n - 1)) / 2 + (n * (n - 1) * (n - 2)) / 3 + (9 * n * (n - 1) * (n - 2) * (n - 3)) / 24;
	}
	cout << ans << endl;
}