斯特林数模板

斯特林数

• 第一类斯特林数
• 第二类斯特林数

第一类斯特林数

求将n个互不相同的球分成k个圆排列的方案数

思路

s[i][j]表示将i个球分成j个圆排列的方案数，当放入第i个球时，可以将其额外新增一个原排列，此时方案数位s[i-1][j-1]，也可以将其插入到前i-1个数的空隙中，由于是圆排列，x个球就有x个空，于是新增了（i-1)*s[i-1][j]种方案。

第一类斯特林数模板题

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int k,n;
const int N=1005;
int s[N][N];
const int mod=1e9+7;
signed main()
{
    cin>>n>>k;
    s[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j];
            s[i][j]%=mod;
        }
    }
    cout<<s[n][k]<<endl;
}
           

第二类斯特林数

求将n个不同的球分成k组的方案数

思路

S[i][j][表示将i个球分成j组的方案数，当放入第i个球时，同第一类斯特林数，可以选择额外生成一个原排列，则方案数为S[i-1][j-1]，也可以将其插入到前j组中，方案数为j*S[i-1][j]。

第二类斯特林数模板

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
int S[N][N];
int n,k;
const int mod=1e9+7;
signed main()
{
    cin>>n>>k;
    S[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            S[i][j]=S[i-1][j-1]+j*S[i-1][j];
            S[i][j]%=mod;
        }
    }
    cout<<S[n][k]<<endl;
    return 0;
}