这篇文章上次修改于 186 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
前言
最近刷模板题,然后刷到了卢卡斯定理,AK了就来写了。
阅读本文你需要的知识
组合计数,MOD运算
正文
卢卡斯定理用于求解大组合数取模的问题,正常的组合数通过递推或者公式计算出,但大组合数会很慢。但当问题规模很大,而模数是一个不大的质数的时候,就不能简单地通过递推求解来得到答案,所以我们的前辈们就发明(发现)了卢卡斯定理,方便我们解决此类毒瘤问题。
卢卡斯定理的定义式如下:
C(m, n) mod p = C(int(m / p), int(n / p)) × C(m mod p, n mod p) mod p
其中int为向下取整,p为质数。
因为 m mod p 和 n mod p 一定比p小,所以可以直接求解C(m mod p, n mod p).
而剩下的C(int(m / p), int(n / p))则继续用卢卡斯定理递归求解。
C语言实现:
#include <stdio.h>
typedef long long ll;
ll a[100010];
ll dpow(ll y, int z, int p) {
y %= p;
ll ans = 1;
for(int i = z; i; i >>= 1 , y = y*y%p)
if(i & 1)
ans = ans * y % p;
return ans;
}
ll C(ll n, ll m, int p) {
if(m > n)
return 0;
return ((a[n] * dpow(a[m], p - 2, p)) % p * dpow(a[n - m], p - 2, p) % p);
}
ll lucas(ll n, ll m, ll p) {
if (m == 0)
return 1;
return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}
int main() {
int T;
ll n, m, p;
scanf("%d", &T);
while (T--) {
scanf("%lld %lld %lld", &n, &m, &p);
a[0] = 1;
for(int i = 1; i <= p; ++i)
a[i] = (a[i - 1] * i) % p;
printf("%lld\n", lucas(n + m, n, p));
}
return 0;
}
没有评论