「学习笔记」斯特林数

发表于 更新于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 2 分钟

第二类斯特林数

第二类斯特林数 {nm}\begin{Bmatrix}n\\m\end{Bmatrix} 表示把 nn 个 不同 的元素划分成 mm 个 相同 的集合中（不能有空集）的方案数。

第二类斯特林数·行

求 {n0},{n1},{n2},…,{nn}\begin{Bmatrix}n\\0\end{Bmatrix},\begin{Bmatrix}n\\1\end{Bmatrix},\begin{Bmatrix}n\\2\end{Bmatrix},\dots,\begin{Bmatrix}n\\n\end{Bmatrix}

1≤n≤2×1051\le n\le 2\times 10^5

这里给出一种二项式反演做法

根据第二类斯特林数的组合意义可以得到

mn=∑i=0m(mi){ni}i!m^n=\sum_{i=0}^m\binom m i \begin{Bmatrix}n\\i\end{Bmatrix}i!

也就是可以有空集的方案数，从 mm 个集合中选出 ii 个不为空的集合，放 nn 个元素， ii 个集合的全排列

设

f(m)=mn,g(m)={nm}m!f(m)=m^n,g(m)=\begin{Bmatrix}n\\m\end{Bmatrix}m!

那么

f(m)=∑i=0m(mi)g(i)g(m)=∑i=0m(−1)m−i(mi)f(i){nm}m!=∑i=0m(−1)m−im!i!(m−i)!in{nm}=∑i=0mini!(−1)m−i(m−i)!f(m)=\sum_{i=0}^m\binom m ig(i) \\ g(m)=\sum_{i=0}^m(-1)^{m-i}\binom m if(i) \\ \begin{Bmatrix}n\\m\end{Bmatrix}m!=\sum_{i=0}^m(-1)^{m-i}\dfrac{m!}{i!(m-i)!}i^n \\ \begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m\dfrac{i^n}{i!}\dfrac{(-1)^{m - i}}{(m-i)!} \\

然后直接 NTT 卷积即可

Code 
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#define ll long long
#define db double
#define gc getchar
#define pc putchar

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; bool f = 0; char c = gc();
        while(!isdigit(c)) f |= c == '-', c = gc();
        while(isdigit(c)) x = x * 10 + c - '0', c = gc();
        if(f) x = -x;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc('0' + x % 10);
    }
}
using namespace IO;

const int N = 2e5 + 5;
const int mod = 167772161;
const int G = 3;
const int Gi = 55924054;

ll add(ll x) {return x < mod ? x : x - mod;}
ll sub(ll x) {return x < 0 ? x + mod : x;}
ll qpow(ll a, int b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}
ll inv(ll x) {return qpow(x, mod - 2);}

int rev[N << 2];

int calclim(int n)
{
    int lim = 1;
    while(lim < n) lim <<= 1;
    return lim;
}

void calcrev(int lim)
{
    for(int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
}

void NTT(ll *a, int lim, int type)
{
    for(int i = 0; i < lim; i++)
        if(i < rev[i]) swap(a[i], a[rev[i]]);
    for(int mid = 1; mid < lim; mid <<= 1)
    {
        ll wn = qpow(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
        for(int i = 0; i < lim; i += (mid << 1))
        {
            ll w = 1;
            for(int j = 0; j < mid; j++, w = w * wn % mod)
            {
                ll x = a[i + j], y = w * a[i + mid + j] % mod;
                a[i + j] = add(x + y);
                a[i + mid + j] = sub(x - y);
            }
        }
    }
    if(type == -1)
    {
        ll limi = qpow(lim, mod - 2);
        for(int i = 0; i < lim; i++) a[i] = a[i] * limi % mod;
    }
    return;
}

void print(ll *a, int n)
{
    for(int i = 0; i < n; i++) write(a[i]), pc(' ');
    pc('\n');
}

ll fac[N], f[N << 2], g[N << 2];

int main()
{
    int n; read(n); n++;
    fac[0] = 1;
    for(int i = 1; i < n; i++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 0; i < n; i++)
    {
        f[i] = qpow(i, n - 1) * inv(fac[i]) % mod;
        g[i] = (i & 1) ? mod - inv(fac[i]) : inv(fac[i]);
    }

    int lim = calclim(n << 1);
    calcrev(lim);
    NTT(f, lim, 1), NTT(g, lim, 1);
    for(int i = 0; i < lim; i++) f[i] = f[i] * g[i] % mod;
    NTT(f, lim, -1);
    
    print(f, n);
    return 0;
}
// A.S.