算法
(前缀和,组合数) O(n2+t)
首先通过组合恒等式 Cmn=Cmn−1+Cm−1n−1 将所有 Cmn 模 k 的余数预处理出来。
然后递推出前缀和:s[i][j]
,表示 Cji,0≤i≤n,0≤j≤min(i,m) 中 k 的倍数的个数。
这里的前缀和虽然是一个三角形,但由于当 n<m 时 Cmn 不存在,所以我们可以直接将其定义成不是 k 的倍数,这样我们就可以通过预处理方形前缀和的方式来求 s[i][j]
了。
二维前缀和递推方法可以参考 AcWing 796. 子矩阵的和。
时间复杂度分析
递推出 Cmn 的时间复杂度是 O(n2),预处理二维前缀和的时间复杂度也是 O(n2)。每次查询时直接查表即可,时间复杂度是 O(1),一共有 t 次询问,因此总时间复杂度是 O(n2+t)。
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;
}
感觉y总代码总是那么简洁,自己写的一团糟
谢谢hh,孰能生巧,加油!
听了好几遍,大概听懂了,但是为什么所有的循环 都跟 m 没关系,最后只有输入涉及到m呢?
因为前面的预处理部分不会涉及到m,只是输出时有关系
哪里听的课?
y总,请问为什么求前缀和的时候j需要<N才能过呢?为啥<=i就不行
回去复习复习前缀和,你没有明白前缀和的边界
我复习了也没有想通,求大佬指点
打表看一下就懂了
因为大于i 的s也是需要用的,用来
s[i][j] = s[i-1][j] + s[i][j-1] + s[i][j] - s[i-1][j-1]
递推这题数据n m顺序是不是干反了 还是 故意折磨弄的
没给反啊。