【题目来源】
https://www.luogu.com.cn/problem/P2822

【题目描述】
组合数​表示的是从n个物品中选出m个物品的方案数。举个例子：从(1,2,3)三个物品中选择两个物品可以有(1,2)，(1,3)，(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数的一般公式：
 
其中。特别地，定义0!=1。
小葱想知道如果给定n，m和k，对于所有的0≤i≤n,0≤j≤min(i,m)，有多少对 (i,j) 满足​是k的倍数，即满足k整除，也就是。

【输入格式】
第一行有两个整数 t，k，其中 t 代表该测试点总共有多少组测试数据。
接下来 t 行，每行两个整数 n，m。

【输出格式】
共 t 行，每行一个整数代表所有的 中有多少对 (i,j) 满足 。

【算法分析】
本题可采用如下方法进行优化。
1.Pascal's Rule（帕斯卡法则）：
2.取模运算规则：https://www.lmlphp.com/user/56/article/item/3205/
本题用到的取模运算规则：
3.前缀和：https://blog.csdn.net/hnjzsyjyj/article/details/120265452
前缀和，无论是一维前缀和还是二维前缀和，通常都用于快速计算区间和。它们的思想都是利用给定的数据预先处理出一个前缀和数组，之后在计算区间和的时候查表，从而可以大大降低算法的时间复杂度。
一维前缀和数组预处理过程：sum[i]=sum[i-1]+a[i]
一维区间和计算过程：sum[y]-sum[x-1]     （y≥x）
二维前缀和数组预处理过程：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
二维区间和计算过程：sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]     （y2≥y1，x2≥x1）  

二维前缀和示意图如下所示。其中绿色区域是保留区域，红色双箭头经过的区域为删除区域。

为了方便记忆，给出二维前缀和的计算公式的助记示意图。如下所示。

 

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=2005;
int c[maxn][maxn];
int s[maxn][maxn];
int ans[maxn][maxn];int t,k,n,m;int main() {cin>>t>>k;for(int i=1; i<maxn; i++) {c[i][0]=1;c[i][i]=1;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<maxn; i++)for(int j=1; j<=i; j++) {s[i][j]=s[i][j-1];if(c[i][j]==0) s[i][j]++;}for(int cnt=1; cnt<=t; cnt++) {cin>>n>>m;int ans=0;for(int i=1; i<=n; i++) {int j=min(i,m);ans+=s[i][j];}cout<<ans<<endl;}return 0;
}/*
in:
2 5
4 5
6 7out:
0
7
*/

【参考文献】
https://www.luogu.com.cn/problem/P2822
https://www.cnblogs.com/OIerShawnZhou/p/7518444.html