本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-12-04 14:59:54

题目大意：

给出 $n$ 和 $k$ 计算满足至少有 $(n-k)$ 个位置的值 $a[i]==i$ 的 $1-n$ 的全排列的个数

题解思路

通过计算，得出递推式：

$p_1 = 0 , p_2 = 1 , p_i = (n - 1) * (p_{i - 1} + p_{i - 2}) (i > 2)$

这样写代码就简单了!

代码：

#include <bits\/stdc++.h>\/\/万能头
using namespace std;
#define ll long long
const int a[5] = {0 , 0 , 1 , 2 , 9};
inline ll c(ll x , ll y) {
	ll re = 1;
	for (ll i = 1; i <= y; ++ i)re *= n - i + 1;
	for (ll i = 1; i <= y; ++ i)re \/= i;
	return re;
}
int main() {
	cin >> n >> k;\/\/输入
	int ans = 1;\/\/别忘了是1
	for (int i = 2; i <= k; ++ i)
		ans += c(n , i) * a[i];
	cout << ans << endl;\/\/输出答案
	return 0;
}