P3807 【模板】卢卡斯定理 / Lucas 定理

传送门

没学过的到这里学，作者太菜了不会证明，只能自己看了。

题目描述

给定整数n , m , p n, m, pn,m,p的值，求出C n + m n m o d p C_{n + m}^n \bmod pCn+mn​modp的值。

输入数据保证p pp为质数。

注:C CC表示组合数。

输入格式

本题有多组数据。

第一行一个整数T TT，表示数据组数。

对于每组数据:

一行，三个整数n , m , p n, m, pn,m,p。

输出格式

对于每组数据，输出一行，一个整数，表示所求的值。

输入输出样例 #1

输入 #1

2 1 2 5 2 1 5

输出 #1

3 3

说明/提示

对于100 % 100\%100%的数据，1 ≤ n , m , p ≤ 10 5 1 \leq n, m, p \leq 10^51≤n,m,p≤105，1 ≤ T ≤ 10 1 \leq T \leq 101≤T≤10。

思路

根据卢卡斯定理来求即可。

代码

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintp,T,n,m,f[100001],inv[100001];intqpow(inta,intb){intans=1;while(b){if(b&1)ans=a*ans%p;a=a*a%p;b>>=1;}returnans;}intC(intn,intm){if(m>n)return0;returnf[n]*qpow(f[m],p-2)%p*qpow(f[n-m],p-2)%p;}intLucas(intn,intm){if(!m)return1;return(C(n%p,m%p)*Lucas(n/p,m/p))%p;}signedmain(){cin>>T;while(T--){cin>>n>>m>>p;f[0]=1;for(inti=1;i<=p;i++)f[i]=f[i-1]*i%p;cout<<Lucas(n+m,m)<<'\n';}return0;}