【题目来源】
洛谷：P4071 [SDOI2016] 排列计数 - 洛谷
【题目描述】
求有多少种 \(1\) 到 \(n\) 的排列 \(a\)，满足序列恰好有 \(m\) 个位置 \(i\)，使得 \(a_i = i\)。
答案对 \(10^9 + 7\) 取模。
【输入】
本题单测试点内有多组数据。
输入的第一行是一个整数 \(T\)，代表测试数据的组数。
以下 \(T\) 行，每行描述一组测试数据。
对于每组测试数据，每行输入两个整数，依次代表 \(n\) 和 \(m\)。
【输出】
共输出 \(T\) 行，对于每组测试数据，输出一行一个整数代表答案。
【输入样例】
5
1 0
1 1
5 2
100 50
10000 5000
【输出样例】
0
1
20
578028887
60695423
【解题思路】
【算法标签】
《洛谷 P4071 排列计数》 #递推# #枚举# #线性递推# #逆元# #各省省选# #2016# #山东#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005, mod = 1e9+7;
int t, n, m;
int fact[N], inv[N], f[N]; // fact:阶乘, inv:阶乘逆元, f:错排数// 快速幂函数
int qmi(int a, int b)
{int mul = 1;while (b){if (b&1) mul = mul * a % mod; // 如果b是奇数，乘上当前的aa = a * a % mod; // a自乘b >>= 1; // b右移一位}return mul;
}signed main()
{cin >> t; // 读入测试用例数量// 初始化阶乘数组fact[0] = fact[1] = 1; // 0! = 1, 1! = 1fact[2] = 2; // 2! = 2// 初始化阶乘的逆元数组inv[0] = inv[1] = 1; // 0!和1!的逆元都是1inv[2] = qmi(2, mod-2); // 计算2!的逆元// 初始化错排数数组f[0] = 1; // 0个元素的错排数为1（空排列）f[1] = 0; // 1个元素的错排数为0f[2] = 1; // 2个元素的错排数为1// 预处理阶乘、逆元和错排数for (int i=3; i<=1000000; i++){fact[i] = fact[i-1] * i % mod; // 计算i! = (i-1)! * iinv[i] = qmi(fact[i], mod-2); // 计算i!的逆元，使用费马小定理f[i] = (i-1) * (f[i-1] + f[i-2]) % mod; // 错排数递推公式}while (t--) // 处理每个测试用例{scanf("%d%d", &n, &m); // 读入n和mint ans;// 计算组合数C(n,m) = n!/(m!*(n-m)!)ans = fact[n] * inv[m] % mod; // n! * (m!)^-1ans = ans * inv[n-m] % mod; // 再乘以((n-m)!)^-1// 计算错排数D_{n-m}，即f[n-m]// 最终答案 = C(n,m) * D_{n-m}ans = ans * f[n-m] % mod;printf("%lld\n", ans);}return 0;
}
【运行结果】
5
1 0
0
1 1
1
5 2
20
100 50
578028887
10000 5000
60695423