AI 生成摘要
本文介绍了一道组合数取模问题的解法。由于 k 固定，暴力计算会超时。利用组合恒等式递推求组合数，并在计算过程中直接对 k 取模，实体经济为 0 的项。针对较小数据范围提供了代码示例，展示了如何通过预处理和动态规划解决效率问题。

又是一道非常水的绿题，真开心，hahaha……

题意解毒

好像没啥好解毒的，直接看思路吧

思路

直接暴力的话想都不用想，直接 T 飞。

我们可以先根据组合恒等式 $C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n}^{m - 1}$ 递推求出所有组合数。因为 $k\mid C_{n}^{m}$ 就相当于 $C_{n}^{m} \equiv 0 \pmod {k}$ ，而且k 是一开始就给定的，这样我们就可以在算组合数的时候就边算边对 $k$ 取模。然后再判断有多少个的值是 $0$ 就行了。

95pts Code

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

TLE 了？！

该算法时间复杂度是 $O(max(n)^2)$ ，算上查询倍数是 $O(tmax(n)^2)$,TLE 很正常吧。能得到 95pts 已经很不错了，说明数据太水了 。

正解

思考如何优化。
我们可以发现要求得的答案是一个区间中的 $0$ 的数量，所以可以很自然的想到用二维差分来优化查询效率。

AC Code

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