先画出杨辉三角，我们发现\(C_{i}^{j}\)都在\(C_{n}^{m}\)的左上角
那么怎么快速的找倍数呢，由于杨辉三角是加法递推下来的，因此从我们可以边递推边取模，如果余数为0则满足。同时维护二维前缀和，ans[i][j]——到了第i行j列的答案数量。
需要注意的：对于每一行，要加一句 ans[i][i+1]=ans[i][i]; 由于j那个地方没有循环到2005 而下一行要用到这个答案 所以要继承。
#include<bits/stdc++.h> #define N 2005 using namespace std; int a[N+500][N+500],ans[N+500][N+500],t,k; void YH_print() { for(int i=0;i<=N;i++) { a[i][0]=1,a[i][i]=1; } for(int i=2;i<=N;i++) { for(int j=1;j<=i;j++) { a[i][j]=(a[i-1][j-1]+a[i-1][j])%k; ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]; if(!a[i][j]) ans[i][j]++; } ans[i][i+1]=ans[i][i];//由于j那个地方没有循环到2005 而二维前缀和又是一个正方形的维护 所以要继承。 } } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>t>>k; YH_print(); while(t--) { int n,m; cin>>n>>m; if(n<m) cout<<ans[n][n]<<'\n'; else cout<<ans[n][m]<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9582002.html
相关资源：各显卡算力对照表！