题解

题目要求统计杨辉三角中 $$\binom{n}{m}$$ 对给定模数 (k) 取模后为 0 的个数。直接按行枚举即可：

1. 用递推式 $$\binom{i}{j} = \binom{i-1}{j} + \binom{i-1}{j-1}$$ 逐行构造杨辉三角，将每个元素对 (k) 取模，得到数组 a[i][j]。
2. 当 a[i][j] == 0 时，在统计矩阵 f 中把这一位置记为 1，并用二维前缀和$$f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + (a[i][j]==0) $$维护到当前行、当前列以内零元素的数量。
3. 由于组合数在一行里只定义到 j <= i，额外把 f[i][i+1] 设成 f[i][i] 方便查询。

这样预处理一次即可回答所有询问：对输入的 \((n, m)\) 输出 \(f[n][\min(n,m)]\)。复杂度 (O(n^2))，对上限 \(n \le 2000\) 可以接受。

#include <bits/stdc++.h>  
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e3 + 10;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
int a[N][N], f[N][N];
int k;
void init() {
	a[1][1] = a[1][0] = 1;
	for (int i = 2; i <= 2e3; i++) {
		a[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			a[i][j] = (a[i - 1][j] + a[i - 1][j - 1]) % k;
			if (!a[i][j]) f[i][j]++;
			f[i][j] = f[i][j] + f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
		}
		f[i][i + 1] = f[i][i];
	}
}
void solve() {
	int t;
	cin >> t >> k;
	init();
	while (t--) {
		int n, m;
		cin >> n >> m;
		cout << f[n][min(n, m)] << endl;
	}
}
signed main() {
	int T = 1;
	//cin >> T;

	while (T--) {
		solve();
	}
	return 0;
}