這道題是問題求解和程序設計的作業題，剛拿到這道題的時候，我完全沒與遞推的概念，第一反應完全是離散數學里面叫得容斥原理，典型的錯排問題，一共有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 閱讀(251)
評論(1) 編輯 收藏 引用 所屬分類:
acm