C++: 卢卡斯定理模板 - 求组合数模质数

题目描述

给定整数 'n', 'm', 'p' 的值，求出 $C_{n + m}^n mod p$ 的值。

输入数据保证 'p' 为质数。

注: 'C' 表示组合数。

输入格式

本题有多组数据。

第一行一个整数 'T'，表示数据组数。

对于每组数据:

一行，三个整数 'n', 'm', 'p'。

输出格式

对于每组数据，输出一行，一个整数，表示所求的值。

样例 #1

样例输入 #1

2
1 2 5
2 1 5

样例输出 #1

3
3

提示

对于 $100%$ 的数据，$1 \leq n, m, p \leq 10^5$，$1 \leq T \leq 10$。

#include <iostream>
using namespace std;

int fac(int n, int p) {
    int res = 1;
    while (n > 1) {
        res = (res * n) % p;
        n--;
    }
    return res;
}

int pow_mod(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;
}

int lucas(int n, int m, int p) {
    int res = 1;
    while (n > 0 && m > 0) {
        int a = n % p;
        int b = m % p;
        if (a < b) {
            return 0;
        }
        res = (res * fac(a, p) * pow_mod(fac(b, p) * fac(a - b, p), p - 2, p)) % p;
        n /= p;
        m /= p;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, p;
        cin >> n >> m >> p;
        cout << lucas(n + m, n, p) << endl;
    }
    return 0;
}