「题解」「HDU3625」Examining the Rooms

HDU3625 Examining the Rooms，第一类斯特林数。

题目链接：HDU3625。

题目

题目描述

有 \(n\) 个房间都被锁上了，开门的钥匙被放在房间里面（每个房间一个），第一个房间的门不能被破坏，求最多破坏 \(k\) 个门，有可能将所有房间都打开的概率。

题解

HDU3625 Examining the Rooms，第一类斯特林数。

关于斯特林数，可以看「OI」斯特林数 Stirling。

思路

考虑要打开 \(i\) 扇门，由于第一个门不能直接打开，所以第一个门一定要与其他门组合在一起，那么根据第一类斯特林数的组合意义，对答案的贡献为 \(\begin{bmatrix}n\\i\end{bmatrix}-\begin{bmatrix}n-1\\i-1\end{bmatrix}\)。

那么答案为
\[\texttt{ans}=\frac{\sum^k _ {i=1}\left(\begin{bmatrix}n\\i\end{bmatrix}-\begin{bmatrix}n-1\\i-1\end{bmatrix}\right)}{n!}\]

预处理 \(n!\) 和第一类斯特林数即可。

代码

#include<cstdio>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=20+5;

ll fac[MAXN],S[MAXN][MAXN];

inline void Init(reg int n){
	fac[0]=1;
	for(reg int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i;
	S[0][0]=1;
	for(reg int i=1;i<=n;++i)
		for(reg int j=1;j<=i;++j)
			S[i][j]=S[i-1][j-1]+(i-1)*S[i-1][j];
	return;
}

int n,k;

int main(void){
	Init(20);
	reg int T=read();
	while(T--){
		n=read(),k=read();
		reg ll cnt=0;
		for(reg int i=1;i<=k;++i)
			cnt+=S[n][i]-S[n-1][i-1];
		printf("%.4lf\n",1.0*cnt/fac[n]);
	}
	return 0;
}