题目链接：组合数问题

这道题可以算当年第二简单的。

这里要用到两个技巧：

1. 用杨辉三角递推计算组合数
2. 运用前缀和
   
   有了这两点，这道题就出来了。
   
   我们先运用杨辉三角推出题目范围内所能用到的所有组合数，然后运用二维前缀和（就是每一行的前缀和），这个前缀和用于保存是k的倍数的数的个数。
   
   下面给代码：

#include<bits/stdc++.h>

using namespace std;

int t,k,f[2010][2010],dp[2010][2010];

int n,m,ans;

int main()

{

    scanf("%d%d",&t,&k);

    for (int i=1;i<=2002;++i) {

        f[i][i]=1;

        f[i][1]=i%k;            //1

    }

    for (int i=2;i<=2002;++i) {

        for (int j=2;j<=i-1;++j) {

            f[i][j]=(f[i-1][j]%k+f[i-1][j-1]%k)%k;

        }

    }

    for (int i=1;i<=2002;++i) {

        for (int j=1;j<=i;++j) {

            if (f[i][j]==0) dp[i][j]=dp[i][j-1]+1;//2

                       else dp[i][j]=dp[i][j-1];

        }

    }

    for (int a=1;a<=t;++a) {

        scanf("%d%d",&n,&m);

        ans=0;

        for (int i=1;i<=n;++i) {

            if (i>m) ans+=dp[i][m];      //3

                else ans+=dp[i][i];

        }

       printf("%d\n",ans);

    }

    return 0;

}

主要讲3点：

1处：这里把杨辉三角中最左边的那一列1扔掉了，因为1一定不会整除k；同时取模，这里便于下面计算前缀和。

2处：计算前缀和，如果当前这个数是0（由于已经对k取模了，所以当且仅当为0是代表能整除），数量等于前一个加一，否则直接把前面的粘过来。

3处：因为是前缀和，直接取最后就行。