用unsigned long long边乘边除计算组合数可避免阶乘中间溢出，核心是递推式C(n,k)=C(n,k-1)×(n−k+1)/k，从C(n,0)=1开始，每步先乘后除，并利用k=min(k,n−k)优化；超100时可用__int128。
用 unsigned long long 做滚动乘除，边算边约分
直接算 n! / (k! * (n-k)!) 必然溢出，哪怕 n 只有 60。关键不是换更大类型，而是避免阶乘中间值——改用递推式：C(n, k) = C(n, k-1) * (n - k + 1) / k，从 C(n, 0) = 1 开始，每步先乘后除，且乘完立刻除，保证每一步结果仍是整数（因为连续 k 个整数之积必被 k! 整除）。
实操要点：
- 务必用
unsigned long long，有符号类型在溢出时是未定义行为 - 乘法前检查是否会溢出：若
res > ULLONG_MAX / (n - k + 1)，则提前返回 0 或抛异常（视需求而定） - 除法必须整除，所以顺序不能颠倒：一定是
res *= (n - k + 1); res /= k;，不能先除后乘（会丢精度） - 利用对称性优化：计算前先令
k = min(k, n - k)，减少循环次数
用 __int128（GCC/Clang）扛住更大的 n
当 n 达到 100 左右，unsigned long long（约 1.8e19）也不够，但又不想上大数库，__int128 是最轻量的出路——它提供约 3.4e38 的范围，轻松覆盖 C(100, 50) ≈ 1e29。
注意点：
立即学习“C++免费学习笔记（深入）”；
-
__int128不是标准 C++，仅 GCC/Clang 支持，MSVC 不行 - 不支持 I/O 直接读写（
cin/cout会失败），输出需手动转字符串 - 编译时加
-std=c++17即可使用，无需额外标志 - 仍建议沿用滚动乘除逻辑，而非直接阶乘，避免无谓的大数运算开销
遇到 n 超过 1000？该用对数或模意义下了
一旦 n > 1000，连 __int128 都不够（C(2000,1000) 超 600 位），此时必须切换思路：
- 如果只要近似值：用
lgamma计算对数差，exp(lgamma(n+1) - lgamma(k+1) - lgamma(n-k+1))，再转double - 如果要求精确值且
n很大：必须引入boost::multiprecision::cpp_int或手写高精度，但性能代价明显 - 如果最终要取模（如
1e9+7）：预处理阶乘及其逆元，用费马小定理求逆元，C(n,k) % MOD = fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD
常见溢出错误现象和调试线索
溢出往往不报错，只给出错误结果，比如 C(67, 33) 在 unsigned long long 下算出来是 0 或负数（实际是高位截断）。典型线索：
- 结果突然变小（尤其在
k接近n/2时） - 相同输入在不同编译器/优化等级下结果不一致（溢出触发未定义行为）
-
assert(res > 0)失败，但逻辑上组合数不可能为 0 - 用
std::numeric_limits<T>::max()手动验证中间值是否超限，比依赖运行时异常更可靠
真正难的不是写出公式，而是判断「当前输入规模下，哪种方法既安全又不过度牺牲性能」——这需要对数值范围、编译器特性和业务场景做具体权衡。
