CF888D题解

· · 题解

题目大意：

给出 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;
}