【题目描述】

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

其中n! = 1×2×···×n

小葱想知道如果给定n,m和k，对于所有的0<=i<= n，0<=j<= min(i,m)有多少对 (i,j)满足是k的倍数。

【输入格式】

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

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

【输出格式】

t行，每行一个整数代表答案。

【样例输入1】

1 2

3 3

【样例输出1】

1

【样例输入2】

2 5

4 5

6 7

【样例输出2】

0

7

【数据范围】

【分析】

首先我们要知道一个关于组合数的递推公式：C(i,j)=C(i-1,j)+C(i-1,j-1)，其实就是杨辉三角，只是初始化不一样。

如果要计算C(2000,2000)，只能用高精度计算，但是这道题并不需要计算出每一个C(i,j)的值，只要知道C(i,j)对于k的余数即可。

于是我们可以设计算法：先计算出每一个C(i,j)对k取模的值，再用f(i,j)表示C(i,j)是否能整除k，是就为1，反之为0，最后用ans(i,j)表示f(1..i,1..j)的和，最后读入n,m就直接输出ans(n,m)即可。

程序中为了减少内存，把ans数组消掉了。

const maxn=2000;var  f,flag:array[0..2001,0..2001]of longint;//其实i和j如果有一个为0，C(i,j)就不存在了，因为分母为零，不过C(0,0)好像是1    i,j,t,k,n,m:longint;begin  read(t,k);  for i:=1 to maxn do begin f[i,1]:=i mod k;f[i,i]:=1; end;    for i:=3 to maxn do      for j:=2 to i-1 do          f[i,j]:=(f[i-1,j]+f[i-1,j-1]) mod k;    for i:=1 to maxn do      for j:=1 to i do          if f[i,j]=0 then flag[i,j]:=1;    fillchar(f,sizeof(f),0);    for i:=1 to maxn do      for j:=1 to maxn do          f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1]+flag[i,j];    for i:=1 to t do begin      read(n,m);        writeln(f[n,m]);    end;end.