题解 P3904 三只小猪
RuntimeErr
2021-07-27 00:20:03
## 第二类斯特林数例题
#### 定义：
$S(n,m)$ 表示将 $n$ 个**两两不同**的元素划分成 $m$ 个**互不区分**的集合的方案数。
#### 递推式：
$$\text{递归边界：}S(n,0)=[n=0],$$
$$S(n,m)=S(n-1,m-1)+m\times S(n-1,m)$$
如何理解？对于选取的第 $n$ 个元素，我们有两种情况：
1. 将其放入一个新的集合，则方案数为 $1\times S(n-1,m-1)=S(n-1,m-1)$。
2. 将其放入现有的一个集合，则有 $m$ 个选择，方案数为 $m\times S(n-1,m)$。
根据加法原理把两种方案数相加即可。
注意：答案过大，需要用高精度运算。
Code:
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
struct node{
int len,num[1000];
}f[60][60];//这里用f数组来表示S
node add(node a,node b){
node res;memset(res.num,0,sizeof res);
res.len=max(a.len,b.len);
for(int i=1;i<=res.len;++i){
res.num[i]+=a.num[i]+b.num[i];
if(res.num[i]>9){
res.num[i+1]+=res.num[i]/10;
res.num[i]%=10;
if(i==res.len)++res.len;
}
}
return res;
}
node mul(int a,node b){
node res;memset(res.num,0,sizeof res);
res.len=b.len;
for(int i=1;i<=res.len;++i){
res.num[i]+=a*b.num[i];
if(res.num[i]>9){
res.num[i+1]+=res.num[i]/10;
res.num[i]%=10;
if(i==res.len)++res.len;
}
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
if(n<m){puts("0");return 0;}
f[0][0].num[1]=1;f[0][0].len=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
f[i][j]=add(f[i-1][j-1],mul(j,f[i-1][j]));
}
}
for(int i=f[n][m].len;i;--i)printf("%d",f[n][m].num[i]);
return 0;
}
```