题目描述
题目来源:提高组 2016 Day2 第一题
难度评价: 比较板子的水题
做题体验:轻松
这是一道快速求组合数的问题,由于数据组数较多,所以可以想到预处理
通常预处理有两种方式,如果直接阶乘需要高精度,过于复杂。
所以,可以转换到组合数公式上 $C_i^j = C_{i-1}^j + C_{i-1}^{j-1}$,由于是加法可以直接取模。
我们已经处理出所有可能出现的组合数了,但是,我们需要求的一个范围,可以通过前缀和来转换。
由于组合数公式的来源是杨辉三角,所以我们需要进行一定的处理边界。
算法1
(二维前缀和) $O(n^2)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int t, k;
int n, m;
int cmd[N][N];
int sum[N][N];
int main()
{
scanf("%d %d", &t, &k);
for (int i = 0; i <= 2000; i ++ ) cmd[i][0] = 1;
for (int i = 0; i <= 2000; i ++ )
for (int j = 1; j <= i; j ++ )
{
cmd[i][j] = (cmd[i - 1][j] + cmd[i - 1][j - 1]) % k;
if (!cmd[i][j]) sum[i][j] = 1;
}
for (int i = 1; i <= 2000; i ++ )
for (int j = 1; j <= 2000; j ++ )
{
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
while (t -- )
{
scanf("%d %d", &n, &m);
printf("%d\n", sum[n][m]);
}
return 0;
}