知识：$$ C_n^m = C_{n-1}^m + C_{n-1}^{m-1} $$
为什么想到用前缀和？因为（1）有很多组测试数据。（2）问的是“对于所有的”。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2000+10;
int t,k,n,m,a[N][N],s[N][N];

int main()
{
    scanf("%d%d",&t,&k);

    //求每一个a[i][j]是否是k的倍数 ,0则是，1则不是. 
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
        {
            if(j==0) a[i][j]=1%k;
            else a[i][j]=(a[i-1][j]+a[i-1][j-1])%k;

        }

    //取反 每一个a[i][j]是否是k的倍数 ,1则是，0则不是.   
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
        {
            if(a[i][j]) a[i][j]= 0;
            else a[i][j]=1; 
        }


    //求前缀和 
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            if(i==0) s[i][j]=a[0][0];
            else if(j==0)  s[i][j]=s[i-1][j]+a[i][j];
            else s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
         } 

    //t个询问 
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",s[n][m]);
    }

    return 0;
}