P3904 三只小猪 题解
bloodstalk
·
·
题解
第二类斯特林数。
Description
第二类斯特林数
定义
将 n 个不同元素，划分为 m 个非空子集的方案数，记作 \begin{Bmatrix}n\\m\end{Bmatrix}。
递推公式
\begin{Bmatrix}n\\m\end{Bmatrix} = \begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}
放到这个题下证明一下。
考虑第 $n$ 个小猪进房间的情况：
1. 若单独进一个房间，前面的 $n-1$ 个小猪就要进 $m-1$ 个房间里，方案数就是 $\begin{Bmatrix}n-1\\m-1\end{Bmatrix}$；
2. 若进已经有小猪的房间里，就先让前 $n-1$ 个小猪进 $m$ 个房间里，第 $n$ 个小猪可以进 $m$ 个房间中任意一个房间，不重不漏，这样的方案数就是 $m\begin{Bmatrix}n-1\\m\end{Bmatrix}$。
分类加法，最后的方案数就是
$$
\begin{Bmatrix}n\\m\end{Bmatrix} = \begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}
$$
# Solution
知道了第二类斯特林数的递推公式，我们就可以对这个题进行求解了。
但是斯特林数的增长比组合数还要快，$n\leq 50$ 就会爆 long long，因此需要高精。
$S_{i,j,k}$ 表示第二类斯特林数 $\begin{Bmatrix}i\\j\end{Bmatrix}$ 的第 $k$ 位是多少，$L_{i,j}$ 表示 $\begin{Bmatrix}i\\j\end{Bmatrix}$ 有多少位，然后高精乘法即可。
# Code
```cpp
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 50 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int n,m;
int S[N][N][105],L[N][N];
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void calc(int x,int y)
{
L[x][y] = max(L[x-1][y-1],L[x-1][y]);
for(re int i=1;i<=L[x][y];i++)
{
S[x][y][i] += S[x-1][y-1][i] + y * S[x-1][y][i];
S[x][y][i+1] += S[x][y][i] / 10;
S[x][y][i] %= 10;
}
if(S[x][y][L[x][y]+1] > 0) L[x][y]++;//看看能不能更新最高位
while(S[x][y][L[x][y]] >= 10)
{
S[x][y][L[x][y]+1] = S[x][y][L[x][y]] / 10;
S[x][y][L[x][y]] %= 10;
L[x][y]++;
}
}
signed main()
{
S[0][0][1] = 1 , L[0][0] = 1;
n = read() , m = read();
if(!m || m > n) return printf("0"),0;//特判等于0的情况
for(re int i=1;i<=n;i++)
for(re int j=1;j<=min(i,m);j++)
calc(i,j);
for(re int i=L[n][m];i>=1;i--) cout << S[n][m][i];
return 0;
}
```