NOIP2016 Day2 T1(组合数+二维前缀和)

用递推式(杨辉三角)来计算$C^m_n$(数组从0开始就是$c(n,m)$,否则$c(n+1,m+1)$),然后维护一个二维前缀和,每个$C^m_n$只要能够整除$k$,置为1,然后处理前缀和即可
注意组合数求解的时候一定要模$k$,并且求解范围不要超出$i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 2000 + 5;
int t;
LL k, c[MAXN][MAXN], a[MAXN][MAXN], qzh[MAXN][MAXN];
void clean() {
ms(c, 0), ms(a, 0), ms(qzh, 0);
}
void solve() {
clean();
for (int i = 1; i <= 2000 + 2; i++) c[i][i] = c[i][1] = 1;
for (int i = 2; i <= 2000 + 2; i++) {
for (int j = 1; j <= i; j++) {//一定要循环到i结束,否则下面c[i][j]==0会出问题
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;//一定要模
if (c[i][j] == 0) a[i][j] = 1;
}
}
for (int i = 1; i <= 2000 + 2; i++) {
for (int j = 1; j <= 2000 + 2; j++) {
qzh[i][j] = a[i][j] + qzh[i - 1][j] + qzh[i][j - 1] - qzh[i - 1][j - 1];
}
}
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
if (m > n) m = n;
printf("%lld\n", qzh[n + 1][m + 1]);
}
}
int main() {
scanf("%d%lld", &t, &k), solve();
return 0;
}

------ 本文结束 ------