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,这样就不会误判了。

代码: