光棍节的快乐
- 描述
-
光棍们，今天是光棍节。聪明的NS想到了一个活动来丰富这个光棍节。
规则如下：
每个光棍在一个纸条上写一个自己心仪女生的名字，然后把这些纸条装进一个盒子里，这些光 棍依次抽取一张纸条，如果上面的名字就是自己心仪的女生，那么主持人就在现场给该女生打电话，告诉这个光棍对她的爱慕之情，并让光棍当场表白，并得到现场所有人的祝福，没抽到的，嘿嘿就可以幸免了。
假设一共有N个光棍,其中有M个没有抽到自己的纸条,求发生这种情况一共有多少种可能.。
- 输入
- 每行包含两个整数N和M(1<M<=N<=20)，以EOF结尾。
- 输出
- 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
- 样例输入
-
2 2
3 2 - 样例输出
-
1
3
这道题考查的是全错位排列公式。题目本身很容易，就是要知道有这么一个经典问题的递推公式。
用A、B、C……表示写着n位友人名字的信封，a、b、c……表示n份相应的写好的信纸。把错装的总数为记作f(n)。假设把a错装进B里了，包含着这个错误的一切错装法分两类：
（1）b装入A里，这时每种错装的其余部分都与A、B、a、b无关，应有f(n-2)种错装法。
（2）b装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）(n-1 )份信纸b、c……装入（除B以外的）n－1个信封A、C……显然这时装错的方法有f(n-1)种。
总之在a装入B的错误之下，共有错装法f(n-2)+f(n-1)种。a装入C，装入D……的n－2种错误之下，同样都有f(n-2)+f(n-1)种错装法，因此:
f(n)=(n-1) [f(n-1)+f(n-2)]
然后需要注意的一点就是，在阶乘的运算中注意运算过程，以防溢出。
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std; int main(){
long long wrong[];
wrong[]=, wrong[]=,wrong[]=;
for(int i=;i<=;i++){
wrong[i] = (i-)*(wrong[i-]+ wrong[i-] );
} int m,n;
while(scanf("%d%d",&n,&m)!=EOF){
double res = ;
for(int i=n,j=;j<=m;j++,i-- ){
res = res*i/j;
} long long res0 = res* wrong[m];
printf("%lld\n",res0); } return ;
}