好题，或许是因为我太菜了
题面
分析
法一：容斥
不难想到用排列组合，问题就转化为：从 kkk 个空中选 xxx 个空，使它们全部填匹配的数字，而剩下的 k−xk-xk−x 个空全都不匹配。
即 ans=C(x,k)×...ans=C(x,k)\times...ans=C(x,k)×...
难点就在后面那里，怎么求出 k−xk-xk−x 个空全都不匹配的方案数。
考虑 A(k−x,n−x)A(k-x,n-x)A(k−x,n−x) 为随便向这里面填数的方案数，显然这里面会有一些数恰巧匹配，所以我们需要减掉一些东西。
考虑 A(k−x,n−x)−C(1,k−x)×A(k−x−1,n−x−1)A(k-x,n-x)-C(1,k-x)\times A(k-x-1,n-x-1)A(k−x,n−x)−C(1,k−x)×A(k−x−1,n−x−1)，限制了一个位置必须匹配，再减去，但这样会多减去重复的。
于是我们需要 容斥，考虑一个序列，枚举 a1a_1a1 减了一次，枚举a2a_2a2 减了一次，所以需要在 a1,a2a_1,a_2a1,a2 同时出现时加一次。同理 a1,a2a_1,a_2a1,a2，a2,a3a_2,a_3a2,a3，a1,a3a_1,a_3a1,a3 同时出现时加了，需要在 a1,a2,a3a_1,a_2,a_3a1,a2,a3 同时出现时减。
所以 ans=C(x,k)×(∑i=0k−xA(k−x−i,n−x−i)×C(i,k−x)×(−1)i)ans=C(x,k)\times(\sum_{i=0}^{k-x}A(k-x-i,n-x-i)\times C(i,k-x)\times (-1)^i)ans=C(x,k)×(∑i=0k−xA(k−x−i,n−x−i)×C(i,k−x)×(−1)i)。
这里用个阶乘逆元，可以做到 O(n)\mathcal {O}(n)O(n)。
Code
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int MAXN = 1e6 + 5, MAXM = 105, Mod = 1e9 + 7;
int n, k, m, jc[MAXN], Inv[MAXN], c, d;
int Quick_Pow(int x, int y) {
int ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = ans * x % Mod;
x = x * x % Mod;
}
return ans;
}
int C(int x, int y) { return jc[y] * Inv[x] % Mod * Inv[y - x] % Mod; }
int A(int x, int y) { return jc[y] * Inv[y - x] % Mod; }
signed main() {
scanf("%lld%lld%lld", &n, &k, &m); jc[0] = 1;
for(int i = 1; i <= n; i ++) jc[i] = jc[i - 1] * i % Mod;
Inv[n] = Quick_Pow(jc[n], Mod - 2);
for(int i = n - 1; i >= 0; i --) Inv[i] = Inv[i + 1] * (i + 1) % Mod;
c = C(m, k);
for(int i = 0; i <= k - m; i ++) {
if(i & 1) d -= A(k - m - i, n - m - i) * C(i, k - m) % Mod, d %= Mod;
else d += A(k - m - i, n - m - i) * C(i, k - m) % Mod, d %= Mod;
}
d = (d % Mod + Mod) % Mod; printf("%lld", c * d % Mod);
return 0;
}
法二：错排
考虑错排一般的模型。给你 nnn 个数字，当且仅当 ai=ia_i=iai=i 时，它是匹配的，要你寻找没有匹配的排列数量。
考虑 dp。
1.给 nnn 号位填数时，所填数字对应的位置|中的数字等于 nnn，即 nnn 与 另一个位置上的数交换了。
这时 dp[n]=dp[n−2]×(n−1)dp[n]=dp[n-2]\times (n-1)dp[n]=dp[n−2]×(n−1)。
2.反之，一时半会也讲不清，我们的重点不是这个，直接给公式，dp[n]=dp[n−1]×(n−1)dp[n]=dp[n-1]\times (n-1)dp[n]=dp[n−1]×(n−1)。
所以 dp[n]=(n−1)×(dp[n−1]+dp[n−2])dp[n]=(n-1)\times (dp[n-1]+dp[n-2])dp[n]=(n−1)×(dp[n−1]+dp[n−2])。
这道题和错排很像，发现在 nnn 中取了 xxx 个数必须合法以后，剩下的 k−xk-xk−x 个位置就是错排的模型，而有 n−kn-kn−k 个位置中的数可以随便选。
令 dp[i][j]dp[i][j]dp[i][j] 为进行到第 iii 个位置，选了 jjj 个不与任何位置匹配的数的方案数。
1.选不与任何位置匹配的数，令其为 a[id]=vala[id]=vala[id]=val，这时，不与任何位置匹配的数肯定会少一个 (valvalval)，但 ididid 又成了新的不与任何位置匹配的数，所以 dp[i][j]=dp[i−1][j]×jdp[i][j]=dp[i-1][j]\times jdp[i][j]=dp[i−1][j]×j。
2.选与某一位置匹配的数。考虑错排。
① nnn 与另一个位置上的数交换（对应上面的第一点），dp[i][j]=dp[i−2][j]×(i−1)dp[i][j]=dp[i-2][j]\times (i-1)dp[i][j]=dp[i−2][j]×(i−1)。
② 对应上面的第二点，dp[i][j]=dp[i−1][j]×(i−1)dp[i][j]=dp[i-1][j]\times (i-1)dp[i][j]=dp[i−1][j]×(i−1)。
发现第二维没动，所以 dp[i]=dp[i−1]×(i+j−1)+dp[i−2]×(i−1)dp[i]=dp[i-1]\times (i+j-1)+dp[i-2]\times(i-1)dp[i]=dp[i−1]×(i+j−1)+dp[i−2]×(i−1)。这里 j=n−kj=n-kj=n−k。
Code
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int MAXN = 1e6 + 5, MAXM = 105, Mod = 1e9 + 7;
int n, k, m, jc[MAXN], Inv[MAXN], c, d, dp[MAXN];
int Quick_Pow(int x, int y) {
int ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = ans * x % Mod;
x = x * x % Mod;
}
return ans;
}
int C(int x, int y) { return jc[y] * Inv[x] % Mod * Inv[y - x] % Mod; }
int A(int x, int y) { return jc[y] * Inv[y - x] % Mod; }
signed main() {
scanf("%lld%lld%lld", &n, &k, &m); jc[0] = 1;
for(int i = 1; i <= n; i ++) jc[i] = jc[i - 1] * i % Mod;
Inv[n] = Quick_Pow(jc[n], Mod - 2);
for(int i = n - 1; i >= 0; i --) Inv[i] = Inv[i + 1] * (i + 1) % Mod;
c = C(m, k); dp[0] = 1;
for(int i = 1; i <= k - m; i ++) dp[i] = dp[i - 1] * (i + n - k - 1) + (i >= 2 ? dp[i - 2] * (i - 1) : 0), dp[i] %= Mod;
printf("%lld", c * dp[k - m] % Mod);
return 0;
}