第一类斯特林数

性质与结论

\left[\begin{matrix} n \cr m \end{matrix}\right] 表示 n 个不同的元素构成 m 个圆排列的数目。

递推式：最后一个元素成单独一个圆排列，有\left[\begin{matrix}n-1 \cr m-1 \end{matrix}\right]种方案；若前n-1个元素已经构成了m个圆排列，最后一个元素有n-1中插入方法。因此

\left[\begin{matrix}n \cr m \end{matrix}\right]=\left[\begin{matrix}n-1 \cr m-1 \end{matrix}\right]+(n-1)\left[\begin{matrix}n-1 \cr m \end{matrix}\right]

重要公式：

x^{\overline{n}}=\sum_i\begin{bmatrix} n \cr i \end{bmatrix}x^i=x(x+1)(x+2)\cdots(x+n-1)

表格(从S(0,0)开始)：

\left[\begin{matrix}1\cr 0&1\cr 0&1&1\cr 0&2&3&1\cr 0&6&11&6&1\cr 0&24&50&35&10&1\cr 0&120&274&225&85&15&1\cr 0&720&1764&1624&735&175&21&1\end{matrix}\right]

倍增法求第一类斯特林数-行

按顺序输出

\begin{bmatrix}n\cr 0\end{bmatrix},\begin{bmatrix}n\cr 1\end{bmatrix},\begin{bmatrix}n\cr 2\end{bmatrix},\dots,\begin{bmatrix}n\cr n\end{bmatrix}

// 省略头文件以及NTT乘法模版

const int N = 1e6 + 50;
int rev[N], fac[N], ifac[N], ni[N];
void init(int len = N - 5) {
    fac[0] = ifac[0] = ni[0] = ni[1] = 1;
    for (int i = 1; i <= len; i++) fac[i] = mul(fac[i - 1], i);
    ifac[len] = inv(fac[len]);
    for (int i = len - 1; i; i--) ifac[i] = mul(ifac[i + 1], i + 1);
    for (int i = 2; i <= len; i++) ni[i] = mul(P - P / i, ni[P % i]);
}

VI solve(int n) {
    VI res;
    if (n == 1) {
        res.push_back(0); res.push_back(1);
        return res;
    }
    if (n & 1) {
        res = solve(n - 1);
        res.resize(n + 1);
        for (int i = n; i; i--) {
            res[i] = (res[i - 1] + mul(res[i], n - 1)) % P;
        }
        return res;
    }
    int mid = n >> 1;
    VI a = solve(mid), b(mid + 1), c(mid + 1);
    for (int i = 0; i <= mid; i++) c[i] = mul(a[i], fac[i]);
    for (int i = 0, p = 1; i <= mid; i++) {
        b[i] = mul(p, ifac[i]); p = mul(p, mid);
    }
    reverse(b.begin(), b.begin() + mid + 1);
    c = c * b;
    for(int i = 0; i <= mid; i++) c[i] = mul(c[i + mid], ifac[i]);
    c.resize(mid + 1); res = a * c;
    return res;
}

int main() {
    int n; scanf("%d", &n);
    init();
    VI ans = solve(n);
    print(ans);
    return 0;
}

分治FFT求第一类斯特林数-行

斯特林数生成函数：

\sum_{i=0}^{n}\begin{bmatrix} n \cr i \end{bmatrix}x^i=x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)

直接分治FFT求各项系数即可。

VI solve(int l, int r, VI &a, VI &b) {
    if (l == r) {
        VI x; x.emplace_back(b[l]); x.emplace_back(a[l]);
        return x;
    }
    int mid = (l + r) >> 1;
    return multiply(solve(l, mid, a, b), solve(mid + 1, r, a, b));
}

int main() {
    scanf("%d", &n);
    VI x(n, 1), y(n);
    for (int i = 0; i < n; i++) y[i] = i;
    VI a = solve(0, n - 1, x, y);
    print(a);
    return 0;
}

第二类斯特林数

性质与结论

\begin{Bmatrix} n \cr m \end{Bmatrix} 表示 n 个不同的元素构成 m 个集合的方案数。

递推式：最后一个元素成单独构成一个集合，有 \begin{Bmatrix}n-1 \cr m-1 \end{Bmatrix} 种方案；若前 n-1 个元素已经构成了 m 个集合，最后一个元素可任意被分配到这 m 个集合中。因此

\begin{Bmatrix}n \cr m \end{Bmatrix}=\begin{Bmatrix}n-1 \cr m-1 \end{Bmatrix}+m\begin{Bmatrix}n-1 \cr m \end{Bmatrix}

另一个递推式：由容斥定理可得：

\begin{Bmatrix}n \cr m \end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m(-1)^i\binom{m}{i}\cdot (m-i)^n

重要公式：

m^n=\sum_{i=0}^{\min(m,n)}\begin{Bmatrix} n \cr i \end{Bmatrix}m^{\underline{i}}=\sum_{i=0}^{\min(m,n)}\begin{pmatrix} m \cr i \end{pmatrix}\begin{Bmatrix} n \cr i \end{Bmatrix}i!

表格(从 S(0,0) 开始)：

\left[\begin{matrix}1\cr 0&1\cr 0&1&1\cr 0&1&3&1\cr 0&1&7&6&1\cr 0&1&15&25&10&1\cr 0&1&31&90&65&15&1\cr 0&1&63&301&350&140&21&1\end{matrix}\right]

求第二类斯特林数-行

m^n=\sum_{i=0}^{m}\left(\begin{matrix} m \cr i \end{matrix}\right)\begin{Bmatrix} n \cr i \end{Bmatrix}i!

设：

f(m)=m^n，g(i)=\begin{Bmatrix} n \cr i \end{Bmatrix}i!

由二项式反演：

g(m)=\sum_{i=0}^{m}\left(\begin{matrix} m \cr i \end{matrix}\right)f(i)

即：

\begin{Bmatrix} n \cr m \end{Bmatrix}m!=\sum_{i=0}^{m}(-1)^{m-i}\left(\begin{matrix} m \cr i \end{matrix}\right)i^n

\begin{aligned}
\therefore \begin{Bmatrix} n \cr m \end{Bmatrix}&=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}\frac{m!\cdot i^n}{(m-i)!\cdot i!}\cr
&=\sum_{i=0}^{m}\frac{(-1)^{m-i}}{(m-i)!}\cdot\frac{i^n}{i!}\cr
&=\sum_{i=0}^{m}\frac{(-1)^{i}}{i!}\cdot\frac{(m-i)^n}{(m-i)!}
\end{aligned}

设：

F=\frac{(-1)^{i}}{i!},\ G=\frac{i^n}{i!}

由 F * G 可得第二类斯特林数-行

模版：求 \begin{Bmatrix} n \cr 0 \end{Bmatrix},\begin{Bmatrix} n \cr 1 \end{Bmatrix},\begin{Bmatrix} n \cr 2 \end{Bmatrix}\cdots \begin{Bmatrix} n \cr n \end{Bmatrix}

// 省略求阶乘逆元、快速幂、多项式乘法模版
int main() {
    scanf("%d", &n);
    init(); //预处理阶乘的逆元
    VI a(n + 1), b(n + 1);
    for (int i = 0; i <= n; i++) {
        if (i&1) a[i] = P - ifac[i];
        else a[i] = ifac[i];
        b[i] = 1LL * ksm(i, n) * ifac[i] % P;
    }
    VI ans = a * b; 
    ans.resize(n+1); print(ans);
    return 0;
}

求第二类斯特林数-列

给定 n,k，对于所有的整数 i\in[0,n]，求出 \begin{Bmatrix} i \cr k \end{Bmatrix}。

// 省略多项式求逆模版
VI solve(int l, int r) {
    if (l == r) {
        VI x; x.emplace_back(1); x.emplace_back(P - l);
        return x;
    }
    int mid = (l + r) >> 1;
    return solve(l, mid) * solve(mid + 1, r);
}

VI init() {
    VI a = solve(1, k), S;
    S.resize(k + 1); a.resize(n + 1);
    S[k] = 1; S *= inverse(a);
    S.resize(n + 1);
    return S;
}

int main() {
    scanf("%d%d", &n, &k);
    VI ans = init();
    print(ans);
    return 0;
}

应用

函数与斯特林数公式相同

CF960G

题目大意：

给你 N,A,B，问从 1 到 N 有多少种排列方式，使得从左边能看到 A 个、右边能看到 B 个。

分析：

设 f[i][j]：i 个里面有 j 个能看见。考虑转移，假设最后一个放的最小，若看得见，则放在首位共 1 种方案；否则看不见，有 n-1 种方案。因此有：f[i][j]=f[i-1][j-1]+(n-1)f[i-1][j]，发现即为第一类斯特林数！

由于最高的一定能被看见，所以把最高的拿掉并以之为分界线，左边能看见 A-1 个，右边能看见 B-1 个。枚举左边的个数 k：

\therefore ans=\sum_{k=0}^{N-1}f[k][A-1]\times f[N-1-k][B-1]\times \binom{N-1}{k}

上式可理解为，N-1 个球中选取一些染成蓝色，剩下的染成红色；把蓝色球分成A-1个圆排列，红色球分成B-1个圆排列；又等同于，N-1个球分成A+B-2个圆排列，其中A-1组染成红色，B-1组染成蓝色。

\therefore ans=\left[\begin{matrix} N-1 \cr A+B-2 \end{matrix}\right] * \left(\begin{matrix} A+B-2 \cr A-1 \end{matrix}\right)

推式子

CF1278F

题目大意：

有 m 张牌，其中一张是王牌。现在你执行 n 次如下操作：洗牌后查看第一张牌是什么。
令 x 为洗牌后第一张牌为王牌的可能次数，现在假设洗牌时 m! 种牌的排列出现的概率均相等，求 x^k 的期望值。

分析：

设：p=\frac{1}{m},\ q = 1- p.

则：

\begin{aligned}
ans&=\sum_{i=0}^{n}\binom{n}{i}\cdot p^i\cdot q^{n-i}\cdot i^k\cr
&=\sum_{i=0}^{n}\binom{n}{i}\cdot p^i\cdot q^{n-i}\cdot \sum_{j=0}^{k}\binom{i}{j}\begin{Bmatrix}k\cr j\end{Bmatrix}\cdot j!\cr
&=\sum_{i=0}^{n}\frac{n!}{i!(n-i)!}\cdot p^i\cdot q^{n-i}\cdot \sum_{j=0}^{k}\frac{i!}{j!(i-j)!}\begin{Bmatrix}k\cr j\end{Bmatrix}\cdot j!\cr
&=n!\sum_{i=0}^{n}\frac{p^i q^{n-i}}{(n-i)!}\cdot \sum_{j=0}^{k}\frac{\begin{Bmatrix}k\cr j\end{Bmatrix}}{(i-j)!}\cr
&=n!\sum_{j=0}^{k}\begin{Bmatrix}k\cr j\end{Bmatrix}\sum_{i=0}^{n}\frac{(n-j)!}{(n-i)!(i-j)!}\cdot \frac{p^i q^{n-i}}{(n-j)!}\cr
&=\sum_{j=0}^{k}\begin{Bmatrix}k\cr j\end{Bmatrix}\frac{n!}{(n-j)!}\sum_{i=0}^{n}\binom{n-j}{n-i}p^i q^{n-i}\cr
&=\sum_{j=0}^{k}\begin{Bmatrix}k\cr j\end{Bmatrix}\binom{n}{j}j!\cdot\sum_{i=j}^{n}\binom{n-j}{i-j}p^i q^{n-i}\cr
&=\sum_{j=0}^{k}\begin{Bmatrix}k\cr j\end{Bmatrix}n^{\underline j}\cdot \sum_{i=0}^{n-j}\binom{n-j}{i}p^{i+j}q^{n-i-j}\cr
&=\sum_{j=0}^{k}\begin{Bmatrix}k\cr j\end{Bmatrix}n^{\underline j}\cdot p^j(p+q)^{n-j}\cr
&=\sum_{j=0}^{k}\begin{Bmatrix}k\cr j\end{Bmatrix}n^{\underline j}\cdot p^j
\end{aligned}