$\newcommand\binom[2]{{#1 \choose #2}}$

我们先考虑暴力，暴力枚举每一个$i,j$暴力算$\binom{i}{j}$时间复杂度为$O(T*N^3)$，显然超时

然后我们发现$N,M \le2000$我们考虑使用组合数的递推公式预处理$\binom{0}{0}$到$\binom{2000}{2000}$。

这里说一下组合数递推公式$\binom{i}{j}=\binom{i-1}{j-1}+\binom{i-1}{j}$可以从组合意义上来理解 我们从$i$个数中选$j$个数，对于每一个数可以分为选与不选两种情况，选的时候即$\binom{i-1}{j-1}$,在剩下的$i-1$个数里选$j-1$个数，不选的时候即$\binom{i-1}{j}$，在剩下的$i-1$个数里选出$j$个数.

但是这样复杂度为$O(T*N^2+N^2)$，依旧无法通过，事实上我们需要一种不需要枚举$i,j$的方法才能通过。

我们发现对于多个询问，$k$始终为定值，于是考虑前缀和优化，设$ans_{i,j}$，在预处理时，若$k|\binom{i}{j}$,则将$ans_{i,j}+1$。然后套用二维前缀和。但是我们发现，二维前缀和递推时 $ans_{i,j}=ans_{i-1,j}+ans_{i,j-1},-ans_{i-1,j-1}+[k|\binom{i}{j}]$，在处理到边界时，我们会用未处理的值(因为此时$<j$)来更新。但是我们又发现

对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i,j)$ 满足 $k|\binom{i}{j}$

于是我们直接将未处理的值设为同一行上一个值

由此即可AC这道题了!

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m,k,c[2008][2008],ans[2008][2008];
void init(){
    c[0][0]=1;
    c[1][0]=c[1][1]=1;
    for(int i=2;i<=2000;i++){
        c[i][0]=1; 
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
            if(c[i][j]==0){
                ans[i][j]++;
            } 
        }
        ans[i][i+1]=ans[i][i]; 
    }
}
signed main(){
    cin>>t>>k;
    init(); 
    while(t--){
        cin>>n>>m;
        if(n<m){
            cout<<ans[n][n]<<"\n";
        } 
        else{
            cout<<ans[n][m]<<"\n"; 
        }
    }
    
    return 0;
}