祝大家新年快乐!!
下边开始正式介绍:斯特林数(Stirling
Number)
定义:第一类斯特林数——给出恰包含 m 个圈的 n 个元素 的排列数目. 斯特林数满足母函数关系。
第二类斯特林数——将p个物体划分成k个非空的不可辨别的(可以理解为盒子没有编号)集合的方法数。
S(p,k)的递推公式是:
S(p,k) = k*S(p-1,k) + S(p-1,k-1) ,1<= k <=p-1
边界条件:
S(p,p) = 1 ,p>=0
S(p,0) = 0 ,p>=1
应用:HDU
3625 Examining the Rooms
斯特林第一类数的应用,根据大神的分析,在这个题目里,因为不能破坏第1个门,所以S(N,K)-S(N-1,K-1)才是能算构成K个环的方法数!就是去掉1自己成环的情况!
AC:
#include <iostream> #include <cstring> #include <iomanip> using namespace std; long long stlen[25][25]; long long f[25]; void stlentable() { stlen[1][1]=1; f[0]=f[1]=1; for(int i=2;i<25;i++) { for(int j=1;j<=i;j++) { stlen[i][j]=stlen[i-1][j-1]+(i-1)*stlen[i-1][j]; f[i]=f[i-1]*i; } } } int main() { stlentable(); int testcase; cin>>testcase; while(testcase--) { int a,b; cin>>a>>b; long long ans=0; for(int i=1;i<=b;i++) { ans+=stlen[a][i]-stlen[a-1][i-1]; } cout<<setiosflags(ios::fixed)<<setprecision(4)<<1.0*ans/f[a]<<endl; } return 0; }