-
分析
很容易想到从 \(0\) 开始枚举 \(a_i \neq i\) 的位置个数一直枚举到 \(k\) 计算每种情况下的答案加在一起即为答案。
对于 \(k\) 确定的情况，\(a_i = i\) 的位置共有 \(C_{n}^{n-k}\) 种情况，剩下的位置要保证 \(a_i \neq i\)。
显然这是一个错排问题，因为 \(k\) 的值很小可以直接枚举打出 \(1、0、1、3、9\) 的表表示长度为 \(0 \sim 4\) 的错排序列个数。
当然也可以使用错排公式 \(D_n = (n - 1)(D_{n - 2} + D_{n - 1})\) 计算。
所以最后的答案为 \(\sum_{i=0}^{k}C_{n}^{n-i} \times D_i\)。
算一下极限数据1000 4，发现答案为 \(373086956251\)，超出 int 范围而又在 long long 范围内，所以计算答案时需要开 long long。 -
代码
#include <iostream>
#define int long long
using namespace std;
constexpr int MAXN(1000007);
inline void read(int &temp) { cin >> temp; }
int d[5] = {1, 0, 1, 2, 9};
int n, k, ans;
inline int calc(int a, int b) {
int res1(1), res2(1);
for (int i(a); i > a - b; --i) res1 *= i;
for (int i(b); i; --i) res2 *= i;
return res1 / res2 * d[b];
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(n), read(k);
for (int i(0); i <= k; ++i) ans += calc(n, i);
cout << ans << endl;
return 0;
}