这道题是问题求解和程序设计的作业题，刚拿到这道题的时候，我完全没与递推的概念，第一反应完全是离散数学里面叫得容斥原理，典型的错排问题，一共有n对新人，有m对是错误的，首先通过c(n,m)选出错误的新人是哪些，然后就是算出这m对新人错误排列的方法。
根据容斥原理的公式推出m对错误的情况有m!-c(m,1)(m-1)!+c(m,2)(m-2)!+.....+(-1)^mc(m,m)0!;
在乘上c(n,m)就好了
化简后得a(n,m)(1-1/1!+1/2!-....+(-1)^m/m!);
算到这里我就犯愁了，这括号了的这些个东西怎么算阿，脑子完全堵住了，缓过神来才发现，要实现它并不困难
程序如下：
1
#include<stdio.h>
2__int64 f(int n,int m){
3 __int64 r,tmp1=1;
4 int i;
5 for(i=n;i>n-m;i--)
6 tmp1*=i;
7 r=tmp1;
8 for(i=1;i<=m;i++){
9 tmp1=(-tmp1)/i;
10 r+=tmp1;}
11 return r;
12}
13int main(){
14 int t,m,n;
15 __int64 result;
16 scanf("%d",&t);
17 while((t--)>0){
18 scanf("%d%d",&n,&m);
19 result=f(n,m);
20 printf("%I64d\n",result);
21 }
22 return 0;
23}
posted on 2008-03-02 17:03
zoyi 阅读(227)
评论(1) 编辑 收藏 引用 所属分类:
acm