HDU 3625( Examining the Rooms 斯特林数的应用 )

spoiler posted @ 2011年4月20日 04:18 in 斯特林数的各种应用 , 2483 阅读

题目:

就是给你N个房间,然后每个房间1把钥匙,你最初手里没有任何钥匙,要靠破门而入!这里只有第一个房间不能破门进去,其他都可以,

给你房间数N,和最多能破门的个数,让你求能全部把房间打开的概率!

题目分析:

又是是我的第一次啊!受教育了?有木有?这种题目是斯特林第一类数的应用,虽然很裸,但是很经典啊 !

首先这题其实让我们求的是给 N个元素,让我们求K个环排列的 方法数。

斯特林第一类数的第推公式:

S(N,0)=0;

S(N,N)=1;

S(0,0)=0;

S(N,K)=S(N-1,K-1)+S(N-1,K)*(N-1);

这个公式的意思是:

当前N-1个数构成K-1 个环的时候,加入第N个 ,N只能构成单环!---S(N-1,K-1)

如果N-1个数构成K个环的时候,加入第N个,N可以任意加入,N-1内的一个环里,所以是--(N-1)*S(N-1,K)

这个题目里,因为不能破坏第1个门:

所以

S(N,K)-S(N-1,K-1)才是能算构成K个环的方法数!就是去掉1自己成环的情况!

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20;
long long f[25],stir[25][25];
int solve(){
	int i,j;
	f[0]=1;
	for(i=1;i<=maxn;i++)
		f[i]=i*f[i-1];
            //因为N有N!种排列顺序,这作为总数
        //计算概率
	for(i=1;i<=maxn;i++)
		stir[i][0]=0;
	stir[1][1]=1;
	for(i=1;i<=maxn;i++)
		for(j=1;j<=i;j++){
			if(i==j)
				stir[i][j]=1;
			else
				stir[i][j]=stir[i-1][j-1]+(i-1)*stir[i-1][j];
		}
	for(i=1;i<=maxn;i++)
		for(j=1;j<=maxn;j++)
			if(stir[i][j]<0)
				stir[i][j]=-stir[i][j];
	return 0;
}
int main(){
	int cas,n,i,k;
	long long sum;
	solve();
	scanf("%d",&cas);
	while(cas--){
		scanf("%d %d",&n,&k);
		sum=0;
		for(i=1;i<=k;i++)
			sum+=stir[n][i]-stir[n-1][i-1];
		printf("%.4lf\n",1.0*sum/f[n]);//因为写成printf("%.4lf\n",(double)sum/f[n]);
		//run time error! 下次一定记好了!
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter