不会组合数基础性质的请转：https://i-beta.cnblogs.com/posts/edit;postId=12653316
首先我们知道，杨辉三角就是组合数，我们把杨辉三角左对齐后
有
1
1 2 1
1 3 3 1
1 4 6 4 1
...
会发现第一列和最后一列的数都是1
其余的数都等于上面的数+左上角的数
可以表示为，c[i][j]=c[i-1][j]+c[i-1][j-1]
再设置一个s数组，表示矩阵和，需要减去s[i-1][j-1]可以联想一下容斥原理
两个矩阵和都包括了s[i-1][j-1]，所以需要减一个
s[i][i+1]=s[i][i];这里是继承上一个矩阵和
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int t,k,n,m; int c[2005][2005],s[2005][2005]; void prepare(); int main(){ memset(c,0,sizeof(c)); memset(s,0,sizeof(s)); cin>>t>>k; prepare(); while(t--){ cin>>n>>m; if(m>n) m=n; cout<<s[n][m]<<endl; } return 0; } void prepare(){ c[1][1]=1; for(int i=0;i<=2000;i++) c[i][0]=1; for(int i=2;i<=2000;i++){ for(int j=1;j<=i;j++){ c[i][j]=(c[i-1][j]+c[i-1][j-1])%k; } } for(int i=2;i<=2000;i++){ for(int j=1;j<=i;j++){ s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; if(c[i][j]==0) s[i][j]+=1; } s[i][i+1]=s[i][i]; } }
原文：https://www.cnblogs.com/liumengliang/p/12823510.html