题解 | 组合数问题-NOIP2016提高组复赛
组合数问题
https://ac.nowcoder.com/acm/contest/264/A
算法知识点: 前缀和，组合数
复杂度： )
解题思路：
首先通过组合恒等式 将所有
模
的余数预处理出来。
然后递推出前缀和：，表示
中
的倍数的个数。
查询时直接查表即可。
C++ 代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 2010;
int c[N][N];
int s[N][N];
int main()
{
int T, k;
scanf("%d%d", &T, &k);
for (int i = 0; i < N; i++)
for (int j = 0; j <= i; j++)
{
if (!j) c[i][j] = 1 % k;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
if (!c[i][j]) s[i][j] = 1;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
if (i) s[i][j] += s[i - 1][j];
if (j) s[i][j] += s[i][j - 1];
if (i && j) s[i][j] -= s[i - 1][j - 1];
}
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
printf("%d\n", s[n][m]);
}
return 0;
} 