C++ 非质数取模程序模板：计算组合数

以下是一个对非质数求取模的 C++ 程序模板：

#include <iostream>
#include <vector>

using namespace std;

// 计算 a^b mod p 的值
int modExp(int a, int b, int p) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

// 计算 a 在模 p 意义下的逆元
int modInverse(int a, int p) {
    return modExp(a, p - 2, p);
}

// 对 a 在模 p 意义下取模
int mod(int a, int p) {
    return ((a % p) + p) % p;
}

// 计算组合数 C(n, m) 在模 p 意义下的值
int comb(int n, int m, int p) {
    vector<int> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % p;
    }
    int invFactM = modInverse(fact[m], p);
    int invFactNM = modInverse(fact[n - m], p);
    return (fact[n] * invFactM % p * invFactNM % p) % p;
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    cout << comb(n, m, p) << endl;
    return 0;
}

该程序模板中的 modExp 函数用于计算 a 的 b 次幂在模 p 意义下的值，modInverse 函数用于计算 a 在模 p 意义下的逆元，mod 函数用于对 a 在模 p 意义下取模，comb 函数用于计算组合数 C(n, m) 在模 p 意义下的值。

在使用该程序模板时，需要注意输入的 n、m、p 均为正整数，且 p 不是质数。