首页 > 代码库 > HDU 3625

HDU 3625

2024-07-26 18:44:59   211人阅读

有点置换群的味道。

当撞开一个门后，能打开一连串的门，即是可以排成一个圈。求的是种数，于是，可以使用第一类斯特林数，求出撞了0~K次的种数。

但是，注意，当第一个门为独自一个圈时，是不可行的，因为这代表第一个门要撞开，这违犯规则。所以，把第一个门独立成圈的情况去掉。即是求出S(N-1,K-1)以前的各种情况了。减去即可。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define LL __int64using namespace std;LL str[21][21];LL cn[21];void initial(){	cn[0]=1;	for(LL i=1;i<=20;i++)	cn[i]=cn[i-1]*i;	for(LL i=0;i<=20;i++){		for(LL j=0;j<=i;j++){			if(i==j)			str[i][j]=1;			else if(j==0)			str[i][j]=0;			else{				str[i][j]=(i-1)*str[i-1][j]+str[i-1][j-1];			}		}	}}int main(){	initial();	int T,n,k;	scanf("%d",&T);	while(T--){		scanf("%d%d",&n,&k);		LL up=0;		LL down=cn[n];		for(int i=0;i<=k;i++)		up+=str[n][i];		for(int i=0;i<=k-1;i++)		up-=str[n-1][i];		double ans=(double)up/(double)down;		printf("%0.4lf\n",ans);	}	return 0;}

　　

HDU 3625


联系
我们