如何计算组合数?

· · 算法·理论

题目简述

给定正整数 nm,求 C_n^m \mod 998244353 的结果。

### 思路 不难发现,题目要求计算组合数。考虑组合数的定义,表示在 $n$ 个元素选出 $m$ 个元素的方案数。 根据乘法原理,我们可以分步考虑问题。对于第 $i$ 步,有 $(n - i + 1)$ 个元素可选,显然结果为 $\prod\limits_{i = 1}^m (n - i + 1)$。 但这样显然会算重,因为选 $m$ 个元素没有先后顺序,于是还要除 $m!$,所以最终答案为: $$\frac{\prod\limits_{i = 1}^m (n - i + 1)}{m!}$$ ### 实现 注意到 $m$ 不大,于是直接根据式子暴力计算即可。时间复杂度 $O(m)$。 ```cpp #include <bits/stdc++.h> using namespace std; const int mod = 998244353; int n, m, ans1 = 1, ans2 = 1; inline int inv(int x, int y = mod - 2){ int mul = 1; while(y){ if(y & 1) mul = 1ll * mul * x % mod; x = 1ll * x * x % mod; y >>= 1; } return mul; } int main (){ cin >> n >> m; for(int i = 1; i <= m; i++) ans1 = 1ll * ans1 * (n - i + 1) % mod; for(int i = 1; i <= m; i++) ans2 = 1ll * ans2 * i % mod; cout << (1ll * ans1 * inv(ans2) % mod) << '\n'; return 0; } ```