1. 题目

传送门=￣ω￣=

2. 题解

感觉自己 noip2016 在仙游。。。
为什么这么水的题目没想出来？当时也学了组合数递推求 $C_n^k$
先预处理出 $C_n^k\ mod\ k$的值，对于询问 n,m，求出有多少个 $C_i^j\ mod\ k(i\leq n,j\leq m)$等于 0 就是答案。
但是如果每次还 O(nm) 地遍历一遍会超时，于是我们搞个 ans[i][j] 表示对于询问 i,j 的答案，很显然这就是个矩阵的前缀和，即：ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+(c[i][j]==0)
需要注意的是我们要设置对于所有的 i<j，c[i][j]=1，这样就不会误判了。

代码：

#include <bits/stdc++.h>
#define NS 2000
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    dig=0;char c;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int t,k,c[NS+5][NS+5],ans[NS+5][NS+5],a,b;
int main()
{
    IN(t),IN(k);
    for(int i=1;i<=NS;i++)
    {
        c[i][0]=1,c[i][1]=i%k;
        for(int j=2;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
    }
    for(int i=1;i<=NS;i++)for(int j=i+1;j<=NS;j++)c[i][j]=1;
    for(int i=1;i<=NS;i++)
        for(int j=1;j<=NS;j++)
            ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+!c[i][j];
    while(t--)IN(a),IN(b),printf("%d\n",ans[a][b]);
    return 0;
}