3.卢卡斯定理
可用于求组合数mod p的值,其公式为:
\[C_{n}^{k}=(C_{\frac{n}{p}}^{\frac{k}{p}}*C_{n\%p}^{k\%p})\% p
\]
\]
上模板:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
int T;
ll n, m, p;
ll j[N];
ll pow(ll a, ll b, ll p)
{
ll res = 1;
for (; b; b >>= 1)
{
if (b & 1)
res = (res * a) % p;
a = a * a % p;
}
return res;
}
ll C(ll n, ll m)
{
if (m > n)
return 0;
return ((j[n] * pow(j[m], p - 2, p)) % p * pow(j[n - m], p - 2, p) % p);
}
ll Lucas(ll n, ll m)
{
if (!m)
return 1;
return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
int main()
{
j[0] = 1;
cin >> T;
while (T--)
{
cin >> n >> m >> p;
for (int i = 1; i <= p; i++)
j[i] = j[i - 1] * i % p;
cout << Lucas(n + m, n) << endl;
}
system("pause");
return 0;
}
原文链接: https://www.cnblogs.com/StungYep/p/12253913.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/326758
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!