$N^2$

预先计算出所有$c[i][j]$,然后如果$c[i][j]\%k==0$,那么我们令$s[i][j]=1$,否则我们令$s[i][j]=0$,那么所求的所有的解即为$s[n][m]$

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int c[N][N],s[N][N];
int main()
{
 
    int t,k,n,m;
    cin>>t>>k;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j) c[i][j]=1%k;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            if(!c[i][j]) s[i][j]=1;//表示当前组合数是k的倍数
        }
    }
    
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(i) s[i][j]+=s[i-1][j]; //左边
            if(j) s[i][j]+=s[i][j-1]; //下边
            if(i&&j) s[i][j]-=s[i-1][j-1];//左下角
        }
    }
    
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        cout<<s[n][m]<<endl;
    }
    return 0;
}