#include <iostream>
using namespace std;
int f[2001][2001];//f[i][j]表示C_i^j mod k
int ans[2001][2001];
int t, k, n, m;
void calc() {
	for (int i = 0; i <= 2000; ++i) f[i][0] = 1;
	for (int j = 1; j <= 2000; ++j) {
		for (int i = j; i <= 2000; ++i) {
			f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
			f[i][j] %= k;
		}
	}
	for (int i = 1; i <= 2000; ++i)
		for (int j = 1; j <= 2000; ++j) {
			ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
			if (f[i][j] == 0 && i >= j) ans[i][j]++;
		}}
int main() {
	cin >> t >> k;
	calc();
	while (t--) {
		cin >> n >> m;
		cout << ans[n][m] << endl;
	}
	return 0;
}

数据范围不大，因此直接预处理出 $2000$ 以内的组合数，运用杨辉三角，同时对 $k$ 取模，可以边计算边取模，否则会超出存储范围。

对于每一次输入的 $n$ 和 $m$，都要从第 $0$ 层开始求，频繁的求和，因此可以用二维前缀和预处理。二维前缀和用的时候保证是一个完整的矩阵，但是杨辉三角显然不是，是一个三角形形状，没关系我们给它没有数字的地方把数字补上，都补 $1$ 就完事了,补成 $1$ 预处理的时候是对 $k$ 取模的，对答案有贡献的都是取模后为 $0$ 的我们补成 $1$ 这样才不会影响最终的答案，can u understand?。

然后对于每一组询问，直接输出答案。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e3 + 5;
int t, k, c[N][N], sum[N][N];
void init()
{
    for (int i = 0; i <= 2000; i++)
    {
        for (int j = 0; j <= 2000; j++)
        {
            if (j > i) c[i][j] = c[i][j - 1];
            else
            {
                if (j == 0 || j == i) c[i][j] = 1;
                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
            }
        }
    }
    for (int i = 1; i <= 2000; i++)
    {
        for (int j = 1; j <= 2000; j++)
        {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (c[i][j] == 0);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t >> k;
    init();
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        cout << sum[n][min(m, n)] << "\n";
    }
    return 0;
}