c++组合数(逆元)代码
时间: 2023-10-16 19:16:50 浏览: 59
```cpp
const int MAXN = 1e6 + 5;
const int MOD = 998244353;
int fac[MAXN], inv[MAXN];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % MOD;
a = 1ll * a * a % MOD;
b >>= 1;
}
return res;
}
void init() {
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
for (int i = MAXN - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int m) {
return n < m ? 0 : 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
```
相关问题
求一个数模逆元的c++代码
以下是求一个数的模逆元的C++代码:
```c++
#include <iostream>
using namespace std;
int modInverse(int a, int m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m;
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
int main() {
int a = 5, m = 7;
cout << "The modulo inverse of " << a << " under " << m << " is " << modInverse(a, m) << endl;
return 0;
}
```
输出结果为:
```
The modulo inverse of 5 under 7 is 3
```
其中,`modInverse(a, m)` 函数用于计算 a 在模 m 意义下的逆元。
逆元代码
以下是求逆元的代码实现:
```python
def mod_inverse(a, m):
"""
求 a 在模 m 意义下的逆元
"""
def extended_euclidean_algorithm(a, b):
if b == 0:
return 1, 0, a
else:
x, y, gcd = extended_euclidean_algorithm(b, a % b)
x, y = y, x - (a // b) * y
return x, y, gcd
x, y, gcd = extended_euclidean_algorithm(a, m)
if gcd != 1:
raise ValueError('a 和 m 不互质')
else:
return x % m
```
其中 `a` 和 `m` 分别是待求逆元的数和模数,函数返回 `a` 在模 `m` 意义下的逆元。如果 `a` 和 `m` 不互质,则会抛出 `ValueError` 异常。