【题目】

传送门

题目描述：

组合数 $C_{n}^{m}$Cnm​ 表示的是从 $n$n 个物品中选出 $m$m 个物品的方案数。举个例子，从 $(1,2,3)$(1,2,3) 三个物品中选择两个物品可以有 $(1,2)$(1,2)，$(1,3)$(1,3)，$(2,3)$(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $C_{n}^{m}$Cnm​ 的一般公式：

$C_{n}^{m}=\frac{n!}{m!(n-m)!}$Cnm​=m!(n−m)!n!​

其中 $n!=1×2×...×n$n!=1×2×...×n；特别地，定义 $0!=1$0!=1。

小葱想知道如果给定 $n$n，$m$m 和 $k$k，对于所有的 $0≤i≤n$0≤i≤n，$0≤j≤min(i,m)$0≤j≤min(i,m) 有多少对 $(i,j)$(i,j) 满足 $C_{i}^{j}$Cij​ 是 $k$k 的倍数。

输入格式：

第一行有两个整数 $t$t，$k$k，其中 $t$t 代表该测试点总共有多少组测试数据，$k$k 的意义见【问题描述】。

接下来 $t$t 行每行两个整数 $n$n，$m$m，其中 $n$n，$m$m 的意义见【问题描述】。

输出格式：
输出 $t$t 行，每行一个整数代表所有的 $0≤i≤n$0≤i≤n，$0≤j≤min(i,m)$0≤j≤min(i,m) 中有多少对 $(i,j)$(i,j) 满足 $C_{i}^j$Cij​ 是 $k$k 的倍数。

样例数据：

【样例$1$1】

输入
1 2
3 3

输出
1

【样例$2$2】

输入
2 5
4 5
6 7

输出
0
7

备注：

【样例$1$1说明】
在所有可能的情况中，只有 $C_2^1$C21​ 是 $2$2 的倍数。

【数据规模与约定】

【分析】

90 pts：

妙啊，暴力 $90$90 分啊

其实在考 $noip$noip 的时候，$90$90 分就约等于满分了吧，反正如果我 $t1$t1 有 $90$90 分了，肯定就把更多的时间花在 $t2,t3$t2,t3 了

要得到这 $90$90 分，我们需要知道一个东西，即 $C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}$Cnm​=Cn−1m​+Cn−1m−1​

是不是很眼熟，对，这就是杨辉三角的递推公式啊

所以我们预处理出 $2000$2000 以内的所有组合数（边做边取模），然后用 O（$nm$nm）查询就行了

100 pts：

我离 $A$A 掉 $t1$t1 只差一个前缀和。。。

由于每次询问都是从 $0$0 开始的，而且没有修改，就想到前缀和

就是用 $ans_{n,m}$ansn,m​ 表示对于询问 $n,m$n,m 的答案（也是预处理出来的）

更新的时候，就是 $ans_{i,j}=ans_{i,j-1}+ans_{i-1,j}-ans_{i-1,j-1}$ansi,j​=ansi,j−1​+ansi−1,j​−ansi−1,j−1​

如果此时 $C_{i}^{j}\% k=0$Cij​%k=0，$ans_{i,j}$ansi,j​ 就加 $1$1

（实在不太理解就画个图吧，画个图应该就明白了）

然后实际操作的时候注意一下边界的细节问题就行了

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2005
using namespace std;
int n,m,t,k;
int C[N][N],ans[N][N];
void init()
{
	int i,j;
	C[0][0]=1;
	for(i=1;i<=2000;++i)
	{
		C[i][0]=1;
		for(j=1;j<=i;++j)
		{
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
			ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
			if(!C[i][j])  ans[i][j]++;
		}
		ans[i][i+1]=ans[i][i];
	}
}
int main()
{
	scanf("%d%d",&t,&k);
	init();
	while(t--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",m>n?ans[n][n]:ans[n][m]);
	}
	return 0;
}