洛谷P1287 盒子与球 数学

第二类斯特林数

将 n 个 互不相同的球 放入 k 个互不相同的盒子中，且不能为空，求方案数

如果盒子相同的话用第二类斯特林数来做

s[n][k] 表示 将 n 个可区分的球 放进 k 个 不可区分的盒子中 的方案数

s[n][k] = s[n-1][k-1] + k*s[n-1][k]

s[n-1][k-1] 表示将 这个球单独列为 一份 ，也就是说这份里面只有一个求

s[n-1][k] 表示将 这个球放到其他份子中，然后总共 有 k个份子可以放

然后 现在 球盒互不相同了，那就乘以 m!好了

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std ;  5  6 inline int read()  7 { 8     char ch = getchar() ;  9     int x = 0 ,f = 1 ;10     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ;ch = getchar() ; }11     while(ch>='0'&&ch<='9') { x = x*10+ch-48 ; ch = getchar() ; }12     return x*f ;13 }14 15 int n,k,ans ;16 int s[11][11] ;  17 18 inline int jiecheng(int n) 19 {20     int ans = 1 ;21     for(int i=2;i<=n;i++) ans*=i ; 22     return ans ; 23 }24 25 int main() 26 {27     n = read() ;  k = read() ;28     s[ 1 ][ 1 ] = 1 ; 29     for(int i=2;i<=n;i++) 30         for(int j=1;j<=i;j++) 31             s[ i ][ j ] = s[i-1][j-1] + j*s[i-1][j] ;32     ans = s[n][k] * jiecheng(k) ;  33     printf("%d\n",ans) ; 34     return 0 ; 35 }