NOIP2016 组合数问题

题目链接：洛谷P2822 组合数问题

打表，可以得到下面的表格

n/m	2	3	4	5
1
2
3
4	6	4
5	10		5
6	15	20	15	6

然后，很容易就能够发现这是一个杨辉三角。

接着，我们用矩阵加法来维护，实现的复杂度。

#include <cstdio>
#include <iostream>
long long triangle[2100][2100], sum[2100][2100];
int t, k, n, m;
int min(int a, int b) {
    if (a < b) return a;
    return b;
}
void make() { //制作杨辉三角与矩阵和
    triangle[1][1] = 1;
    for (int i = 0; i <= 2000; i++) {
        triangle[i][0] = 1;
    }
    for (int i = 2; i <= 2000; i++) {
        for (int j = 1; j <= i; j++) {
            triangle[i][j] = (triangle[i - 1][j - 1] + triangle[i - 1][j]) % k;
        }
    }
    
    for (int i = 2; i <= 2000; i++) {
    //printf("%d\n", t);
        for (int j = 1; j <= i; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            if (triangle[i][j] == 0) sum[i][j]++;
        }
        sum[i][i + 1] = sum[i][i];
    }
}
int main() {
    scanf("%d %d", &t, &k);
    make();
    for (int i = 1; i <= t; i++) {
        //printf("1\n");
        int n, m;
        scanf("%d %d", &n, &m);
        if (m > n) m = n;
        printf("%lld\n", sum[n][m]);
    }
    return 0;
}