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$个,所以累加即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信