错排例题1

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

    Input
    输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。 



    Output
    对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。 



    Sample Input
    2

2 2
3 2

    Sample Output
    1

3

代码如下

#include<stdio.h>
int main()
{
 int n,m,i,t;
 long long sum1,sum2;
 long long a[100];
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d%d",&n,&m);
  sum1=1;
  sum2=1;
  a[1]=0;
  a[2]=1;
  for(i=3;i<=20;i++)
  {
   a[i]=(i-1)*(a[i-1]+a[i-2]);
  }
  for(i=1;i<=m;i++)
     sum2*=i;
  for(i=n;i>n-m;i--)
     sum1*=i;
  printf("%lld\n",sum1/sum2*a[m]);
 }
 return 0;
}

其中用到了一个错排公式
a[i]=(i-1)*(a[i-1]+a[i-2])

还涉及到了排列组合。。。。

程序中的sum1就相当于分子
sum2就相当于分母
最后分析下题目，一共有n个新郎，有m个新郎选错了新娘，也就是相当于有m个数排错了位置，套用公式求出a[m]；