$$【组合数学】专题笔记目录$$

第一眼以为是什么神题。
看一眼数据范围吧，$n,m \leq 2000$，这不是连 $O(nm)$ 数组都能开的下吗？
那就直接暴力求出组合数，然后暴力看哪些是 $k$ 的倍数。
对于一次询问，可以用前缀和来维护，$O(1)$ 查询。

#include <bits/stdc++.h>
using namespace std;
const int N = 2015;
int n, m, c[N][N];
int t, k;
int s[N][N];
int main() {
    scanf("%d%d", &t, &k);
    for (int i = 0; i <= 2000; i++)
        for (int j = 0; j <= i; j++) {
            if (!j) c[i][j] = 1;
            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 = 1; i <= 2000; i++)
        for (int j = 1; j <= 2000; j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    while (t--) {
        scanf("%d%d", &n, &m);
        printf("%d\n", s[n][m]);
    }
    return 0;
}