题目描述

组合数 Cmn 表示的是从 n 个物品中选出 m 个物品的方案数。 

举个例子，从 (1, 2, 3) 三个物品中选择两个物品可以有 (1, 2), (1, 3), (2, 3) 这三种选择方法。 

根据组合数的定义，我们可以给出计算组合数 Cmn 的一般公式：

Cmn=n!m!(n−m)!
其中 n! = 1 × 2 × ⋅ ⋅ ⋅ × n。 

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

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

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

输出格式
共 t 行，每行一个整数代表所有的 0 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 有多少对 (i, j) 满足 Cji 是 k 的倍数。

数据范围
1≤n,m≤2000,2≤k≤21,1≤t≤104

样例

blablabla

心得

刚开始想的时候发现要判断所有 0 ≤ i ≤ n, 0 ≤ j ≤ min(i, m)中的C[i][j],这时间复杂度直接O(n^2),
那就一定有O(n)的做法,要mod k==0,就想到lucas,但是万一n,m太大,好像也不行。这时候想会不会是用一些
小结论,组合数的结论不多,一般常用的就是c[i][j]=c[i-1][j]+c[i-1][j-1],这是组合数I,可是想到好像这
时间复杂度也是O(n^2便放弃了。然后看了y总的代码,woc这预处理好厉害

  for (int i = 0; i < N; i ++ )
  {
        for (int j = 0; j <= i; j ++ )
        {
            if (!j) c[i][j] = 1 % k;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;

            if (!c[i][j]) s[i][j] = 1;//如果余数为0,那就是满足了,记录一下
        }
   }

这里由于是二维数组的前缀和,所以需要用到二维前缀和

二维数组的前缀和
 for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
        {
            if (i) s[i][j] += s[i - 1][j];//除i行
            if (j) s[i][j] += s[i][j - 1];//除j列
            if (i && j) s[i][j] -= s[i - 1][j - 1];//重复的i-1行,i-1列
        }

这种非模板题需要好好思考,尤其数论的一些结论要熟练应用,想这题其实就是用了一个简单的结论
只是自己知道它却没想到用它来预处理。思维还是不够!以后碰到多组测试数据的问题留意预处理的