题解

思路分析

本题要求统计满足 $C_i^j \bmod k = 0$ 的有序对 $(i,j)$ 的个数，其中 $0 \leq i \leq n$，$0 \leq j \leq \min(i, m)$。

核心思路

1. 预处理组合数

使用 杨辉三角 递推计算组合数模 $k$ 的结果：

$$C_i^j = (C_{i-1}^j + C_{i-1}^{j-1}) \bmod k$$

2. 二维前缀和优化统计

定义 $f[i][j]$ 表示满足 $C_{i'}^{j'} \bmod k = 0$ 且 $i' \leq i$，$j' \leq j$ 的有序对个数。

使用二维前缀和递推：

$$f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + [C_i^j \bmod k = 0] $$

其中 $[C_i^j \bmod k = 0]$ 表示当 $C_i^j$ 是 $k$ 的倍数时值为 1，否则为 0。

3. 查询答案

对于每组询问 $(n, m)$，答案为 $f[n][\min(n, m)]$。

样例说明

以样例1为例：$k=2, n=3, m=3$

杨辉三角模2：

    j=0  j=1  j=2  j=3
i=0:  1
i=1:  1    1
i=2:  1    0    1
i=3:  1    1    1    1

其中 $C_2^1 = 2 \equiv 0 \pmod{2}$（是2的倍数）。

统计 $0 \leq i \leq 3, 0 \leq j \leq \min(i, 3)$ 中为0的个数：只有 $(2, 1)$ 一个，所以答案是 $1$。

前缀和数组 $f$：

    j=0  j=1  j=2  j=3
i=0:  0    0    0    0
i=1:  0    0    0    0
i=2:  0    1    1    1
i=3:  0    1    1    1

查询 $f[3][3] = 1$。

算法步骤

1. 预处理阶段（只需要执行一次）：

   • 使用杨辉三角计算 $a[i][j] = C_i^j \bmod k$（$i, j \leq 2000$）
   • 同时计算二维前缀和 $f[i][j]$
   • 处理边界：$f[i][i+1] = f[i][i]$（因为 $C_i^j$ 在 $j > i$ 时无意义）

2. 查询阶段：

   • 对于每组询问 $(n, m)$，直接输出 $f[n][\min(n, m)]$

关键优化

• 预处理一次，多次查询：由于 $t$ 可能很大（最多 10000 组），预处理组合数和前缀和能避免重复计算
• 模运算：在计算组合数时直接对 $k$ 取模，避免大数运算
• 边界处理：$f[i][i+1] = f[i][i]$ 确保查询 $\min(n, m)$ 时不会越界

复杂度分析

• 预处理时间复杂度：$O(n^2)$（$n = 2000$）
• 单次查询时间复杂度：$O(1)$
• 总时间复杂度：$O(n^2 + t)$
• 空间复杂度：$O(n^2)$

#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;
}

题解

题目要求统计杨辉三角中 $$\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;
}