算法知识点: 前缀和,组合数
复杂度:
解题思路:
首先通过组合恒等式 将所有 模 的余数预处理出来。
然后递推出前缀和:,表示 中 的倍数的个数。
查询时直接查表即可。
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; }