题目描述

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

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

输入描述:

第一行有两个整数 t，k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见 「题目描述」。
接下来 t 行每行两个整数 n，m，其中 n，m 的意义见「题目描述」。

输出描述:

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

示例1

输入
1 2
3 3
输出
1

示例2

输入
2 5
4 5
6 7
输出
0
7
说明
在所有可能的情况中，只有是 2 的倍数。

备注

3 ≤ n, m ≤ 2000, 2 ≤ k ≤ 21, 1 ≤ t ≤ 10000

解答

首先我们来看一个有趣的东西

1 1 1 1 2 1 1 3 3 1

1 4 6 4 1

是不是很眼熟！！这就是一个杨辉三角

所以c(i,j)的值就是第i行第j列

预处理的时候膜?K就好了

那么问题来了，预处理好杨辉三角形，还有T组询问怎么办？？？

我们可以用一个叫做矩阵和的东西（就是下面的S数组）给个口诀吧，上加左 减左上 加自己

这样看预处理只需要的时间而面对T次询问，每次询问只需要O（1）的时间就可以回答，是不是超级方便！！！

下面粘一波代码 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t,k,n,m;
int c[2005][2005],s[2005][2005];
void prepare();
int main(){
//    freopen("problem.in","r",stdin);
//    freopen("problem.out","w",stdout);
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    cin>>t>>k;
    prepare();
    while(t--){
        cin>>n>>m;
        if(m>n) m=n;
        cout<<s[n][m]<<endl;
    }    
    return 0;
} 
void prepare(){
    c[1][1]=1;
    for(int i=0;i<=2000;i++) c[i][0]=1;
    for(int i=2;i<=2000;i++){
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
        }
    }
    for(int i=2;i<=2000;i++){
        for(int j=1;j<=i;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            if(c[i][j]==0) s[i][j]+=1;
        }
        s[i][i+1]=s[i][i];
    }
}



来源：Arthur_L