组合数学推推推最后，推得要求C（n+m，m）%p
其中n，m小于10^9,p小于1^5
用Lucas定理求（Lucas定理求nm较大时的组合数）
因为p数据较小可以直接阶乘打表求逆元
求逆元时，由费马小定理知道p为素数时，a^p-1=1modp可以写成a*a^p-2=1modp
所以a的逆元就是a^p-2,
可以求组合数C（n，m）%p中除法取模,将其转化为乘法取模
即 /(m!*(n-m)!)=*(m!*(n-m)!)^p-2
- #include <iostream>
- #define ll long long
- const int N=1e5+5;
-
- using namespace std;
- ll fac[N],p;
- void init()
- {
- fac[0]=1;
- for(int i=1;i<=p;i++)
- fac[i]=fac[i-1]*i%p;
- }
- ll qpow(ll a,ll b)
- {
- ll ans=1;
- a%=p;
- while(b)
- {
- if(b&1)
- {
- ans=ans*a%p;
- }
- b>>=1;
- a=a*a%p;
- }
- return ans;
- }
- ll C(ll a,ll b)
- {
- if(a<b) return 0;
- return fac[a]*qpow(fac[b]*fac[a-b],p-2)%p;
- }
- ll Lucas(ll a,ll b)
- {
- if(b==0) return 1;
- return (C(a%p,b%p)*Lucas(a/p,b/p))%p;
- }
- int main()
- {
- int T;
- ll n,m;
- cin>>T;
- while(T--)
- {
- cin>>n>>m>>p;
- init();
- cout<<Lucas(n+m,m)<<endl;
- }
- return 0;
- }
hdu 3037 费马小定理+逆元求组合数+Lucas定理
原文：https://www.cnblogs.com/yzm10/p/8763194.html
