题意描述

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

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

根据组合数的定义，我们可以给出计算组合数$C_n^m$的一般公式： $C_n^m = \frac{n!}{m!\times(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)$满足$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)$ 满足 $C_i^j$是 $k$ 的倍数。

Input & Output ‘s examples

Input ‘s eg 1

1 2
3 3

Output ‘s eg 1

Input ‘s eg 2

2 5
4 5
6 7

Output ‘s eg 2

0
7

数据范围和约定

分析

组合数学入门题。

根据Pascal公式，即 $C_n^m = C_{n - 1} ^ {m - 1} + C_{n - 1}^{m}$

可以在$O(n^2)$的时间内预处理出$C_i^j \bmod k$的值。

~~然后暴力统计，你就拿了90分~~

之后使用前缀和$num_{s , i}$表示对于每一个$1 < j < i$，有多少个$C_s^j \bmod k = 0$，每一次询问时$O(n)$查询即可。

时间复杂度为$O(t \times n)$，而本题数据范围较小，足以通过。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 2010

using namespace std;

ll t , HA , n , m;
ll c[N][N];
ll num[N][N];

void get_num(int n , ll HA){
    c[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j ++){//预处理组合数表
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];    
            c[i][j] %= HA;   //由于模运算对加法，减法，乘法封闭，所以直接判断是否可以整除即可
        }
    }
    for(int i = 1; i <= n; i ++){   //简单的憨憨前缀和
        for(int j = 1; j <= i; j ++){
            num[i][j] = num[i][j - 1];
            if(c[i][j] == 0){   //如果可以整除，可行方案就+1
                num[i][j] ++;
            }
        }
    }
    return ;
}

int main(){
    cin >> t >> HA;
    get_num(2001 , HA);
    for(int i = 1; i <= t; i ++){
        ll ans = 0;
        cin >> n >> m;
        for(ll j = 1; j <= n; j ++){    //处理每一次询问
            ans += num[j][min(j , m)];
        }
        cout << ans << "\n";
    }
    return 0;
}