组合数的公式，可谓人所共知。
计算机中组合数的求法，可谓多种。但是，对于特别大的组合数及其取模，我们就要用到著名的卢卡斯定理（Lucas）了。
卢卡斯定理是这样的：
但在代码实现中，我们只要知道
C（n,m）%p=C(n%p,m%p)*lucas(n/p,m/p)%p即可。
我们看一道模板题：
洛谷3807模板卢卡斯定理
给定n,m,p(1\le n,m,p\le 10^51≤n,m,p≤105)
求 C_{n+m}^{m}\ mod\ pCn+mm? mod p
保证P为prime
C表示组合数。
一个测试点内包含多组数据。
输入格式：
第一行一个整数T(T\le 10T≤10)，表示数据组数
第二行开始共T行，每行三个数n m p，意义如上
输出格式：
共T行，每行一个整数表示答案。
2 1 2 5 2 1 5
3 3
思路：计算一遍1到P的阶乘模P后的值，然后卢卡斯定理，用费马小定理求个逆元，就出来了。不过嘛，这个板子有个bug，就是必须写Lucas(n+m,min(n,m))才能过，
若只写Lucas(n+m,n)会WA掉一个点，写Lucas(n+m,m)则会WA掉4个点。
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int maxn=1e5+3; ll jc[maxn]; ll n,m,p; ll ksm(ll a,ll b) { ll c=a,ans=1; while(b) { if(b&1)ans=ans*c%p; c=c*c%p; b>>=1; } return ans; } ll C(ll n,ll m) { if(m>n)return 0; return ((jc[n]*ksm(jc[m],p-2))%p*ksm(jc[n-m],p-2)%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() { int T; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld",&n,&m,&p); jc[1]=1; for(int i=2;i<=(int)p;i++)jc[i]=(jc[i-1]*i)%p; printf("%lld\n",lucas(n+m,min(n,m))); } return 0; }
而我今日才知道，杨辉三角与组合数的奇妙联系
杨辉三角的形式是这样的：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
如果把最上边的点设为F[0][0],那么就会发现，F[N][M]即为C（N,M）的值。
由于杨辉三角的递推关系式为
F[I][J]=F[I-1][J-1]+F[I-1][J]
这也侧面证明了组合数的性质C(n,m)=C(n-1,m-1)+C(n-1,m)
妙啊，完全相符。
柱子发言：就是这么妙。
再看一道题：
洛谷2822组合数问题
组合数 C_n^mCnm? 表示的是从 nn 个物品中选出 mm 个物品的方案数。举个例子，从 (1,2,3)(1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 C_n^mCnm? 的一般公式：
C_n^m=\frac{n!}{m!(n-m)!}Cnm?=m!(n?m)!n!?
其中 n!=1\times2\times\cdots\times nn!=1×2×?×n；特别地，定义 0!=10!=1。
小葱想知道如果给定 n,mn,m 和 kk，对于所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j)(i,j) 满足 C_i^jCij? 是 kk 的倍数。
输入格式：
第一行有两个整数 t,kt,k，其中 tt 代表该测试点总共有多少组测试数据，kk 的意义见问题描述。
接下来 tt 行每行两个整数 n,mn,m，其中 n,mn,m 的意义见问题描述。
输出格式：
共 tt 行，每行一个整数代表所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j)(i,j) 满足 C_i^jCij? 是 kk 的倍数。
【样例1说明】
在所有可能的情况中，只有C_2^1 = 2C21?=2是2的倍数。
【子任务】
利用杨辉三角的思想，这题的思路就很清晰了：利用递推式，直接把1000*1000的表打出来。
但是询问怎么办呢？
又一个好东西登场了，它叫杨辉三角的矩阵前缀和。
这道题中，设he[i][j]为题目所问的答案，则它可以这样求：
he[i][j]=he[i][j-1]+he[i-1][j]-he[i-1][j-1];
if(f[i][j]==0)he[i][j]++;
减去he[i-1][j-1]是因为在he[i][j-1]+he[i-1][j]过程中，它被重复计算了。
还有一条很重要：由于杨辉三角的每行个数是递增的，所以需写一句he[i][i+1]=he[i][i]以备下一行计算he[i+1][i+1]时使用。
就达到了O(1)的时间复杂度。爵士：“学习真是无止境啊。只可惜我们不与霸天虎比学习。”
上代码！！
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int T,k; int yhsj[2003][2003];long long he[2003][2003]; int n,m; int main() { scanf("%d%d",&T,&k); yhsj[0][0]=yhsj[1][0]=yhsj[1][1]=1; for(int i=2;i<=2000;i++) { yhsj[i][0]=1; for(int j=1;j<=i;j++) yhsj[i][j]=(yhsj[i-1][j]+yhsj[i-1][j-1])%k; } for(int i=2;i<=2000;i++) { for(int j=1;j<=i;j++) { he[i][j]=he[i-1][j]+he[i][j-1]-he[i-1][j-1]; if(!yhsj[i][j])he[i][j]++; } he[i][i+1]=he[i][i];//推它下一行有用 } while(T--) { scanf("%d%d",&n,&m); if(m>n)printf("%lld\n",he[n][n]); else printf("%lld\n",he[n][m]); } return 0; }
这就是组合数、杨辉三角和前缀和之间的巧妙联系。
原文：https://www.cnblogs.com/czktransformers/p/9899051.html