题意简述
Kelly 寄出去 \(n\) 封邀请函，但她希望只有小于等于 \(m\) 个人收到他们自己的邀请函（即有至少 \(n-m\) 个人收到了别人的邀请函）。
思路形成
容易发现，这道题是一个典型的错排题，我们只需要分别求出 \(n-m\) 个元素到 \(n\) 个元素的错排即可。
接下来为错排的推导，我们令 \(f[x]\) 表示 \(x\) 个元素的错排。
这时候第 \(x\) 号元素不能在第 \(x\) 个位置上，它排在了另一个位置上，令这个位置为 \(y\)，则 第 \(y\) 号元素出现了两种可能性。
- \(y\) 号元素恰好排在了第 \(x\) 个位置上，此时相当于剩下的元素错排的情况，共 \(f[x-2]\) 种。
- \(y\) 号元素并没有排在第 \(x\) 个位置上，此时如果我们把 \(y\) 就看作 \(x\)，这个问题就变成了除了 \(x\) 以外所有元素的错排，共 \(f[n-1]\) 种
由于 \(y\) 号元素的选取共有 \(x-1\) 种，可以得到最后的递推公式。
\[f[x]=(x-1)\times(f[x-1]+f[x-2])
\]
代码细节
由于每一个人都是不一样的，因此计算答案时还要乘上选出人的方案数，即当有 \(a\) 个人没有收到自己的邀请函时，答案应该为 \(C^{a}_{n} \times f[a]\)。
AC 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=29;
ll C[N][N],cuo[N];
ll n,m;
void init(){
for(ll i=1;i<=20;i++){
C[i][0]=1;
for(ll j=1;j<=i;j++){
C[i][j]=C[i][j-1]*(i-j+1)/j;
}
}
cuo[0]=1;
cuo[2]=1;
for(ll i=3;i<=20;i++){
cuo[i]=(i-1)*(cuo[i-1]+cuo[i-2]);
}
}
void solve(){
while(cin>>n>>m){
ll ans=0;
for(ll i=m;i>=0;i--){
ans+=C[n][i]*cuo[n-i];
}
cout<<ans<<endl;
}
}
int main(){
init();
solve();
return 0;
}