洛谷P1287 盒子与球数学

洛谷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 <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 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
",ans) ; 
34     return 0 ; 
35 }

洛谷P1287 盒子与球 数学

洛谷P1287 盒子与球数学