FZU 2020 组合 Lucas的应用

本文主要是介绍FZU 2020 组合 Lucas的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值!

Lucas的证明：点击打开链接

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 150000;typedef long long ll;ll pow_mod(ll a,ll b,ll p){if (b == 0)return 1;if (b == 1)return a % p;ll t = pow_mod(a,b/2,p);t = t * t % p;if (b & 1)t = (t * a) % p;return t;
}ll cm(ll n,ll m,ll p){ll a,b,ans = 1;for (ll i = 1; i <= m; i++){a = (n+i-m) % p;b = i % p;ans = ans * (a * pow_mod(b,p-2,p) % p) %p;}return ans;
}ll Lucas(ll n,ll m, ll p){if (m == 0)return 1;else return (Lucas(n/p,m/p,p)*cm(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);printf("%lld\n",Lucas(n,m,p));}return 0;
}

这篇关于FZU 2020 组合 Lucas的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---