Hdu 3625 Examining the Rooms[第一类斯特林数]

本文主要是介绍Hdu 3625 Examining the Rooms[第一类斯特林数]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目意思：

n(n <= 20)个房间。n把钥匙。每个房间有一把钥匙。一把钥匙只能开一把锁。

现在一个人手里没有钥匙，他可以强行打开一个门，然后拿出这个房间内的钥匙。不能够强行打开第一个门。。。

问最多强行打开k(k <= n)个房间的门的情况下，可以全部打开所有门的概率。。

分析：第一类斯特林数的小小应用。。。

我们知道所有的钥匙放置的情况为n！种。。

那么我们只需要求解出在最多强行打开k个门的情况下，能够把所有门打开的种数。。需要注意的是1号门不能强行打开。。

我们可以求解出强行打开k个门后，所有门都能打开的种数。然后，减去强行打开1号门在内的情况。。

那么强行打开1号门的种数这么求解呢？就是n - 1个钥匙成  k - 1环的种类数。。

组合数学继续中。。。。。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
#define INT long longconst int N = 23;
INT s[N][N], d[N];void Init()
{s[1][0] = 0; s[1][1] = 1;for(INT i = 2; i <= 20; i ++){s[i][0] = 0;for(INT j = 1; j < i; j ++)s[i][j] = (i - 1) * s[i - 1][j] + s[i - 1][j - 1];s[i][i] = 1;}d[0] = 1;for(int i = 1; i <= 20; i ++)d[i] = d[i - 1] * i;
}int main()
{Init();int T;scanf("%d", &T);while(T --){int n, k;scanf("%d %d", &n, &k);INT ans = 0;for(int i = 1; i <= k; i ++){ans += s[n][i] - s[n - 1][i - 1];}printf("%.4lf\n", 1.0 * ans / d[n]);}return 0;
}

------>

小小的第一类斯特林数的应用。。。

这篇关于Hdu 3625 Examining the Rooms[第一类斯特林数]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---