洛谷P5239 回忆京都

和 NOIP2016TG 组合数问题 差不多是一样的……

首先要知道杨辉三角和组合数之间的关系

看一下数据范围，很明显要避免重复计算，而且查询的复杂度要非常小

一看n, m <= 1000

这明显是一个前缀和……够开二维数组

然而计算前缀和的时候会出现负数（窝70分就是栽在这的qaq比赛过后才查出来），解决方法(()%mod+mod)%mod

单点查询O(1)，预处理O(nm)，能过

// luogu-judger-enable-o2

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include <cstdio>

const int mod = 19260817;

int C[1010][1010], sum[1010][1010];

int main() {

    for(int i = 0; i <= 1000; i++) {

        C[i][0] = C[i][i] = 1;

        for(int j = 1; j < i; j++) {

            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;

        }

    }

    for(int i = 1; i <= 1000; i++) {

        for(int j = 1; j <= 1000; j++) {

            sum[i][j] = ((sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + C[i][j]) % mod + mod) % mod;

        }

    }

    int q;

    scanf("%d", &q);

    int n, m;

    while(q--) {

        scanf("%d%d", &n, &m);

        if(n <= 0 || m <= 0) {

            puts("0");

            continue;

        }

        printf("%d\n", sum[m][n]);

    }

    return 0;

}