UVA11282 题解

题意简述

Kelly 寄出去 \(n\) 封邀请函，但她希望只有小于等于 \(m\) 个人收到他们自己的邀请函（即有至少 \(n-m\) 个人收到了别人的邀请函）。

思路形成

容易发现，这道题是一个典型的错排题，我们只需要分别求出 \(n-m\) 个元素到 \(n\) 个元素的错排即可。

接下来为错排的推导，我们令 \(f[x]\) 表示 \(x\) 个元素的错排。

这时候第 \(x\) 号元素不能在第 \(x\) 个位置上，它排在了另一个位置上，令这个位置为 \(y\)，则 第 \(y\) 号元素出现了两种可能性。

1. \(y\) 号元素恰好排在了第 \(x\) 个位置上，此时相当于剩下的元素错排的情况，共 \(f[x-2]\) 种。
2. \(y\) 号元素并没有排在第 \(x\) 个位置上，此时如果我们把 \(y\) 就看作 \(x\)，这个问题就变成了除了 \(x\) 以外所有元素的错排，共 \(f[n-1]\) 种

由于 \(y\) 号元素的选取共有 \(x-1\) 种，可以得到最后的递推公式。

代码细节

由于每一个人都是不一样的，因此计算答案时还要乘上选出人的方案数，即当有 \(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;
}