贴代码

#include<bits/stdc++.h>
using namespace std ;
const int maxs = 2010 , TIL = ( 1 << 28 )  ;
long long Ans[maxs][maxs] ;
long long C[maxs][maxs] ;
long long T , K ; 
int n , m ;
int main(){
	scanf("%lld %lld" , &T , &K) ;
 	C[0][0] = C[1][0] = C[1][1] = 1 ;
  	for(int i = 2 ; i <= maxs - 1 ;i ++ ) {
    	C[i][0] = 1 ;
    	for(int l = 1 ; l <= i ; l ++ ){
      		C[i][l] = ( C[i - 1][l - 1] + C[i - 1][l] ) % K ;
      		Ans[i][l] = Ans[i - 1][l] + Ans[i][l - 1] - Ans[i - 1][l - 1] ;
      		if(!C[i][l]) Ans[i][l] ++ ;
    	} Ans[i][i + 1] = Ans[i][i] ;
  	}
	while(T -- ){
		scanf("%d %d" , &n , &m) ;
		if(n <= m) printf("%lld\n" , Ans[n][m] ) ;
		else printf("%lld\n" , Ans[n][n] ) ;
	} 
	return 0 ;
}

就是前缀和加杨辉三角的思路