【题目来源】
https://www.luogu.com.cn/problem/P2822
https://www.acwing.com/problem/content/525/
【题目描述】
组合数表示的是从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）
二维前缀和示意图如下所示。其中绿色区域是保留区域，红色双箭头经过的区域为删除区域。
为了方便记忆，给出二维前缀和的计算公式的助记示意图。如下所示。
下面代码中，s[i][j] 是前缀和，表示 中 k 的倍数的个数。
注意，由于当 n<m 时， 不存在，所以我们可以直接将其定义成不是 k 的倍数。
【算法代码】
#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 7
out:
0
7
*/
【参考文献】
https://www.acwing.com/problem/content/798/
https://www.acwing.com/solution/content/3157/
https://www.luogu.com.cn/problem/P2822
https://www.cnblogs.com/OIerShawnZhou/p/7518444.html
