题目
分析
我将本题作为数论中“排列组合”的第一题。
这道题要拿到100分，是有一定的挑战的。单纯的暴力算法会有超时的测试用例。
我们先看基础部分。
排列数的计算
如果使用标准的组合公式：\(C_n^m=\frac{n!}{m!\cdot (n-m)!}\)，是不合理的。参考杨辉三角的样子，我们需要用到一个递推关系：
\(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++)
{
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;
}
}整除计数的预计算
对于求模的问题，能尽早求模总是好的，而且本题只要求统计能被k整除的个数，所以可以先预统计杨辉三角中（也就是对应不同的\(C_m^n\)）每一行能被k整除的个数。
for (int i = 0; i < MAXN; i++)
{
int count = 0;
for (int j = 0; j <= i; j++)
{
if (C[i][j] == 0)
{
count++;
}
}
row_count[i] = count;
}这样一来，所有的预计算就都完成了。
针对每次查询的处理
每次查询都会给出两个数字：m和n，且\(m\le n\)。显然，我们需要累加到n行为止的，所有的\(C_n^m\)的计数。对于某一行i：
- 如果\(i\gt m\)，那么只要加到
m列为止——总共是m+1列。这个数字没有统计过，所以要重新循环加一次。 - 否则，只要直接加统计好的
row_count[i]即可——又“偷（jia）懒（su）”一次。
答案
思考
这道题目的难点在于要100分通过，就必须有预处理的做法。