预处理杨辉三角， 每次转移时把相加后的值对k取模， 结果用二维前缀和记录。 时间复杂度 O ( n m + T ) O(nm+T) O(nm+T) 代码：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long long a[3010][3010],q[3010][3010]; long long n,t,k,m,ans; int main() { cin>>t>>k; a[0][0]=1,a[1][0]=1,a[1][1]=1; for(int i=2; i<=2000; i++) { a[i][0]=1; for(int j=1; j<=i; j++) { a[i][j]=(a[i-1][j-1]+a[i-1][j])%k; if(a[i][j]==0) q[i][j]++; q[i][j]=q[i][j]+q[i-1][j]+q[i][j-1]-q[i-1][j-1]; } q[i][i+1]=q[i][i]; } for(int w=1; w<=t; w++) { cin>>n>>m; if(m>n) cout<<q[n][n]<<endl; else cout<<q[n][m]<<endl; } return 0; }