HDU 3625 第一类斯特林数

题目链接：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!

 #include <bits/stdc++.h>

 using namespace std;

 long long fac[];

 long long stir[][];

 void init() {

     fac[] = ;

     for(int i=;i<;i++)

         fac[i] = i*fac[i-];

     memset(stir,,sizeof(stir));

     stir[][] = ;

     stir[][] = ;

     for(int i=;i<;i++) {

         for(int j=;j<=i;j++)

             stir[i][j] = stir[i-][j-] + (i-)*stir[i-][j];

     }

 }

 int main()

 {

     init();

     int t;

     scanf("%d",&t);

     while(t--) {

         int n,k;

         scanf("%d%d",&n,&k);

         long long cnt = ;

         for(int i=;i<=k;i++)

             cnt+= stir[n][i] - stir[n-][i-];

         printf("%.4lf\n",1.0*cnt/fac[n]);

     }

     return ;

 }