第一类斯特林数递推式为 s(n,k) = s(n−1,k−1) + (n−1)·s(n−1,k)，边界 s(0,0)=1，n>0时s(n,0)=0，k>n时s(n,k)=0；第二类为 s(n,k) = s(n−1,k−1) + k·s(n−1,k)，边界同理。
第一类斯特林数的递推公式怎么写
第一类斯特林数 s(n, k)（无符号记作 c(n, k)）表示将 n 个元素排成 k 个非空循环排列的方案数。它的标准递推关系是：
s(n, k) = s(n-1, k-1) + (n-1) * s(n-1, k)
边界条件为：s(0, 0) = 1，且当 n > 0 时 s(n, 0) = 0；当 k > n 时 s(n, k) = 0。
这个递推的直观解释是：第 n 个元素要么单独构成一个新循环（贡献 s(n-1, k-1)），要么插入到前 n-1 个元素已形成的任意一个循环的任意位置——共 n-1 个可插间隙（每个已有循环长度为 L 就有 L 个插入点，总和正好是 n-1），所以是 (n-1) * s(n-1, k)。
- 用二维数组实现时注意：
s[i][j]依赖s[i-1][j-1]和s[i-1][j]，必须按行从小到大填 - 若只需求单行（如所有
s(n, k)fork=0..n），可用一维滚动数组，但要从后往前更新j，避免覆盖未使用的旧值 - 无符号第一类斯特林数增长极快，
int很快溢出，建议用long long或高精度（如__int128在支持平台）
第二类斯特林数的递推公式怎么写
第二类斯特林数 S(n, k) 表示将 n 个**互异**元素划分为 k 个**非空无序**子集的方案数。它的标准递推式是：
S(n, k) = S(n-1, k-1) + k * S(n-1, k)
边界条件： S(0, 0) = 1，S(n, 0) = 0（n > 0），S(0, k) = 0（k > 0）。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
含义是：第 n 个元素要么自成一个新子集（对应 S(n-1, k-1)），要么加入已有的 k 个子集中的任意一个（共 k 种选择），故加 k * S(n-1, k)。
- 同样适合二维 DP 填表；若只需第
n行，一维数组可从后往前更新 -
S(n, k)的最大值出现在k ≈ n / ln 2附近，n=50时就超1e15，别用int - 注意和贝尔数区别：
B(n) = sum_{k=0}^n S(n,k)，别把求和漏掉
为什么递推时容易算错下标或初值
常见错误不是公式记错，而是初始化和索引越界。比如：
- 把
s(0,0)=1忘了，导致整张表全零 - 数组开成
s[n+1][k+1]却用0..n-1索引，漏掉最后一行 - 误以为
s(1,1)=0（实际是 1），因为混淆了有符号/无符号定义（C++ 中通常用无符号版本） - 在循环中写
for (int j = 1; j ，但没处理 <code>j == 0或j > i的边界，导致未初始化内存参与运算
建议初始化整个二维数组为 0，再显式设 s[0][0] = 1，其余靠递推生成。
C++ 实现时要注意哪些类型与性能细节
递推本身是 O(n²) 时间、O(n²) 空间，但空间可优化到 O(n)。关键实操点：
- 别用
vector<vector long>></vector>存大表（如n=10000），内存爆炸；改用两行滚动数组或仅存一行 - 若需多次查询，预计算好整个表（
n ≤ 5000可行），否则每次临时算太慢 - 对模意义下的计算（如
MOD = 1e9+7），加法和乘法后必须取模，(n-1) * s[n-1][k]容易溢出，应写成1LL * (n-1) % MOD * s[n-1][k] % MOD - 第一类斯特林数有符号版本满足
s_signed(n,k) = (-1)^(n-k) * s_unsigned(n,k)，别混用
最常被忽略的是：两种斯特林数都**不满足对称性**（即 s(n,k) ≠ s(k,n)），也不满足简单单调性，查表时务必核对 n 和 k 的大小关系。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
