题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3625

 

题意： 

n个房间，房间里面放着钥匙，允许破门而入k个，拿到房间里面的钥匙后可以打开对应的门，但是1号门不能破门而入，求这样检查完所有房间，概率是多少？

 

分析：

钥匙随机放到房间，全排列有n!；

n个房间，破k个门进入，就是第一类斯特林数S(n,k)；

但是，第一个门不能破门而入，就是要减去S(n-1,k-1)；

然后求和SUM = S(n,i)  {1<=i<=k}

概率就是 SUM / N!

1 #include 
      
        2  3 using namespace std; 4  5 long long fac[21]; 6 long long stir[21][21]; 7  8 void init() { 9     fac[1] = 1;10     for(int i=2;i<21;i++)11         fac[i] = i*fac[i-1];12 13     memset(stir,0,sizeof(stir));14     stir[0][0] = 1;15     stir[1][1] = 1;16 17     for(int i=2;i<21;i++) {18         for(int j=1;j<=i;j++)19             stir[i][j] = stir[i-1][j-1] + (i-1)*stir[i-1][j];20     }21 22 }23 int main()24 {25     init();26     int t;27     scanf("%d",&t);28     while(t--) {29         int n,k;30         scanf("%d%d",&n,&k);31 32         long long cnt = 0;33         for(int i=1;i<=k;i++)34             cnt+= stir[n][i] - stir[n-1][i-1];35 36         printf("%.4lf\n",1.0*cnt/fac[n]);37 38     }39     return 0;40 }