算法

(前缀和，组合数) $O(n^2 + t)$

首先通过组合恒等式 $C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$ 将所有 $C_n^m$ 模 $k$ 的余数预处理出来。

然后递推出前缀和：s[i][j]，表示 $C_i^{j}, 0 \le i \le n, 0 \le j \le min(i, m)$ 中 $k$ 的倍数的个数。

这里的前缀和虽然是一个三角形，但由于当 $n < m$ 时 $C_n^{m}$ 不存在，所以我们可以直接将其定义成不是 $k$ 的倍数，这样我们就可以通过预处理方形前缀和的方式来求 s[i][j] 了。

二维前缀和递推方法可以参考 AcWing 796. 子矩阵的和。

时间复杂度分析

递推出 $C_n^m$ 的时间复杂度是 $O(n^2)$，预处理二维前缀和的时间复杂度也是 $O(n^2)$。每次查询时直接查表即可，时间复杂度是 $O(1)$，一共有 $t$ 次询问，因此总时间复杂度是 $O(n^2 + t)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010;

int c[N][N];
int s[N][N];

int main()
{
    int T, k;
    scanf("%d%d", &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] + c[i - 1][j - 1]) % k;

            if (!c[i][j]) s[i][j] = 1;
        }

    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;
        scanf("%d%d", &n, &m);

        printf("%d\n", s[n][m]);
    }

    return 0;
}