通过发现，数据范围只有a, b <= 2000, 故可以预处理出来所有的C(a, b)的组合模以k的结果，查询O(1)时间。

故时间复杂度为O(N^2),空间复杂度(N^2).

代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2020;

int T, k;
int c[N][N], f[N][N];

void init()
{
    memset(c, -1, sizeof c); //初始化

    for(int i = 0; i < N; i ++ )
        for(int j = 0; j <= i; j ++ )
            if(i == j || !j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;//k的倍数则为0

    //前缀和矩阵
    for(int i = 1; i < N; i ++ )
        for(int j = 1; j < N; j ++ )
            f[i][j] = (c[i][j] == 0) + f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
}

int main()
{
    cin >> T >> k;

    init(); //预处理

    while(T -- )
    {
        int a, b;
        cin >> a >> b;
//         b = min(a, b);
        cout << f[a][b] << endl;
    }

    return 0;
}

觉得不错给个赞哟👍👍