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

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

#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;
}
------ 本文结束 ------