https://www.luogu.org/problemnew/show/P2822（题目传送）
先了解一下有关组合数的公式：（m在上，n在下）
发现组合数的递推的直观图像形式就是杨辉三角（第i行第j列的数等于C（i-1,j-1））
由于题目要求多组组合数，便可以递推组合数做预处理（直接用通项公式算什么的太粗暴（慢）了）。一看数据范围，保证让普通范围溢出的节奏啊，但定心一看，我们只用知道每个组合数是否能整除k就可，所以可以每次递推算组合数时模k。 TIP：递推不要忘了初始状态（边界）
求出组合数后，发现如果对每次询问都从头到尾扫一遍的话保准会超时，便想到了一个能有效减少查询统计时的复杂度，每一次查询O(n)降到O(1)的神器——前缀和。求一个矩阵的前缀和，只要记住公式：上加左，减上左，加自己。
AC代码如下：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int c[2002][2002],n[10001],m[10001],dp[2001][2001]; 5 int main() 6 { 7 int t,k,mmax=0,nmax=0; 8 cin>>t>>k; 9 for(int i=1;i<=t;i++) 10 { 11 scanf("%d%d",&n[i],&m[i]); 12 if(nmax<n[i]) nmax=n[i]; 13 if(mmax<m[i]) mmax=m[i]; 14 } 15 c[1][1]=1; 16 int mmaxb=mmax; 17 if(mmax>nmax) mmax=nmax+1; 18 else mmax++; 19 for(int i=2;i<=nmax+1;i++) 20 for(int j=1;j<=min(i,mmax);j++) 21 { 22 c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; 23 if(!c[i][j]) dp[i-1][j-1]=1; 24 }//这里用杨辉三角递推的组合数，***需要多做一行***，其实没有直接推组合数方便。 25 for(int j=1;j<=mmaxb;j++) dp[0][j]+=dp[0][j-1]; 26 for(int i=1;i<=nmax;i++) 27 for(int j=0;j<=mmaxb;j++) 28 { 29 if(!j) dp[i][j]+=dp[i-1][j]; 30 else 31 dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; 32 } 33 for(int i=1;i<=t;i++) cout<<dp[n[i]][m[i]]<<endl; 34 return 0; 35 }
原文：https://www.cnblogs.com/InductiveSorting-QYF/p/10623670.html