[数据结构与算法]数论——卢卡斯（Lucas）定理（板子）

Lucas定理：

$C_a^b$ $mod$ $p$ $=$ $$\begin{gathered} C_{b/p}^{a/p}?C_{a \\ \mathrm{m}\mathrm{o}\mathrm{d}p}^{b \\ \mathrm{m}\mathrm{o}\mathrm{d}p} \end{gathered}$$ $mod$ $p$

Lucas板子：

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

Lucas例题

Saving Beans HDU - 3037

ac代码

#include <bits/stdc++.h>

using namespace std;
//组合数求余
typedef long long LL;

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

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

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖