第二类斯特林数学习笔记

置顶 | Posted on | In | Views:

第二类斯特林数

定义

第二类斯特林数$S(n,m)$定义为把$n$个球放入$m$个盒子中，所有盒子均不为空的方案数，其中球不带标号，而盒子是带标号的。

递推求法

根据定义，就能得到第二类斯特林数的递推求法，只需要枚举最后一个球放在哪个集合里即可。

组合求法

而第二类斯特林数还可以用组合意义来求得。
假设我们现在有$n$个无标号球，随意放在$m$个带标号的盒子中，显然方案数可以为$m^n$
而我们再枚举有几个非空盒子，用第二类斯特林数计算，可以得到

这个式子是一个二项式反演的经典式子，我们二项式反演一下

快速求$S(n,1..m)$

发现上面组合求法中，可以把第二类斯特林数写成卷积的形式。

令$A(x)=\frac{(-1)^x}{x!},B(x)=\frac{x^n}{x!}$
$S(n,m)=A(m-j)*B(j)$
用$NTT/FFT$就可以在$O(n*logn)$的时间内求出。

例题

题目链接

BZOJ 5093

做法

显然每个点的贡献是独立的，考虑每个点的贡献，枚举有几条边与他相连，其他与他不相连的边随便。

由于有$n$个点，所以乘个$n$就好了。
定义$f(n,m)$为$\sum\limits_{i=0}^{n}i^m*\binom{n}{i}$
我们只有求出$f(n-1,k)$上面的问题就能解决了。
根据我们前面的式子，上面的$i^m$可以用斯特林数展开。

改为先枚举$j$

观察一下后面这个$\sum\limits_{i=0}^{n}\binom{n}{i}*\binom{i}{j}$是什么
可以看成在$n$个物品中选出$j$个，剩下的随意，那么

所以

这样的话我们在用$NTT$算出第二类斯特林数，剩下的项都可以快速算出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (1000005)
using namespace std;
const int P=998244353;
int n,k,lim,d,invL,tot,CC,mi,inv2;
int f[N<<1],g[N<<1],R[N<<1],A[N],inv[N],jc[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline void NTT(int *f,int G){
    for (int i=0;i<lim;i++){
        if (i>R[i]) swap(f[i],f[R[i]]);
    }
    for (int i=1;i<lim;i<<=1){
        int w0=ksm(G,(P-1)/(i<<1));
        for (int j=0;j<lim;j+=(i<<1)){
            int w=1;
            for (int k=j;k<j+i;k++){
                int t=1ll*f[k+i]*w%P;
                f[k+i]=Inc(f[k],P-t);
                f[k]=Inc(f[k],t);
                w=1ll*w*w0%P;
            }
        }
    }
    if (G!=3){
        for (int i=0;i<lim;i++) f[i]=1ll*f[i]*invL%P;
    }
}
int C(int a,int b){
    return 1ll*jc[a]*inv[a-b]%P*inv[b]%P;
}
int main(){
    read(n),read(k);
    if (k==0){
        printf("%lld",1ll*ksm(2,n-1)*n%P*ksm(2,1ll*(n-1)*(n-2)/2%(P-1))%P);
        return 0;
    }
    for (lim=1;lim<2*k+2;lim<<=1);
    invL=ksm(lim,P-2);
    for (int i=0;i<lim;i++) R[i]=(R[i>>1]>>1)|((i&1)*lim>>1);
    A[0]=A[1]=1;
    for (int i=2;i<=k;i++) A[i]=1ll*(P-P/i)*A[P%i]%P;
    inv[0]=1;
    for (int i=1;i<=k;i++) inv[i]=1ll*inv[i-1]*A[i]%P;
    jc[0]=1;
    for (int i=1;i<=k;i++) jc[i]=1ll*jc[i-1]*i%P;
    f[0]=1;
    g[0]=0;
    d=1;
    for (int i=1;i<=k;i++){
        d=P-d;
        f[i]=1ll*d*inv[i]%P;
        g[i]=1ll*ksm(i,k)*inv[i]%P;
    }
    NTT(f,3),NTT(g,3);
    for (int i=0;i<lim;i++) f[i]=1ll*f[i]*g[i]%P;
    NTT(f,ksm(3,P-2));
    CC=1;
    mi=ksm(2,n-1);
    inv2=ksm(2,P-2);
    for (int j=0;j<=min(n-1,k);j++){
        tot=Inc(tot,1ll*f[j]*CC%P*jc[j]%P*mi%P);
        CC=1ll*CC*A[j+1]%P*(n-j-1)%P;
        mi=1ll*mi*inv2%P;
    } 
    printf("%lld",1ll*tot*n%P*ksm(2,1ll*(n-1)*(n-2)/2%(P-1))%P);
    return 0;
}