题面

题目描述 组合数 $C_n^m$ ​ 表示的是从 nn 个物品中选出 mm 个物品的方案数。举个例子，从 (1,2,3)(1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $C_n^m$的一般公式： \(C_n^m=\frac{n!}{m!(n-m)!}\) 其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$

小葱想知道如果给定 n,m和 k，对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 (i,j)(i,j) 满足 $C_i^j$是 $k$ 的倍数。

输入输出格式

输入格式：

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

输出格式： 共 $t$ 行，每行一个整数代表所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$中有多少对 (i,j)(i,j) 满足 $C_i^j$是 k 的倍数。

样例输入

1 2
3 3

样例输入2

2 5
4 5
6 7

样例1输出

1

样例2输出

0
7

解答

其实看到组合数，应该联想到两个东西:\(C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}\) 和\(C^m_n=\frac{n!}{m!(n-m)!}\) 对于公式法(第二个)，明显是不行的，看数据范围，2000，没搞。并且公式法也没有很好的把已知的数据用起来，造成了一定的信息浪费。好的算法一定信息复用做的很好那么，该怎么办呢？我们看看第一个公式，那不就是杨辉三角？？？对的！看到组合就一定要和杨辉三角结合起来。于是这道题就要使用杨辉三角来计算！但是又有一个问题了，2000的数据范围，肯定会溢出，怎么办呢？仔细看看题，有多少是k的倍数，有因为mod运算对加减乘是开放的（就是可以稍加思索的乱模），那么我们就可以对k一路进行取模下来，如果结果是c[i][j]=0,那么就说明$C_i^j$是k的倍数。 你以为就完了吗？当然没有！我们看看查询组数，感到了世态炎凉以及GGF对我的智商歧视。但是，我们还有一个神奇的东西：前缀和！应该说是二维前缀和！这样我们提前预处理出一个c数组来存储取模过后的杨辉三角数值，然后用一个s数组来，用s[i][j]表示n=i,m=j的时候的符合条件的数据组数，做到了$O(n^2)$预处理，$O(1)$的查询。下面是代码

# include<iostream>
# include<string.h>
using namespace std;
int c[2015][2015];
int s[2015][2015];
int n,m,k,t;
int main(void) {
    ios::sync_with_stdio(false);
    cin >> t >> k;
    for (int i = 0; i <= 2000; i++)
        c[i][0] = c[i][i] = 1;
    for (int i = 1; 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 = 1;i<=2000;i++){
        for(int j = 1;j<=2000;j++){
            s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和的使用
            if(c[i][j]==0&&j<=i){//如果这个位置也是k的倍数的话，要在s上把自己加上去，注意，j<=i,不然就是没有计算过，肯定是0，这样的话就会出错。
            //而i，j都跑到2000是为了防止GGF坑人出现m>n的情况(虽然题面中说了不可能)，反正不这么写就不对
                s[i][j]++;
            }
        }
    }
    while(t--){
        cin>>n>>m;
        cout<<s[n][m]<<endl;
    }
    return 0;
}