Luogu P2822 组合数问题

思路

组合数的话，首先肯定是想到杨辉三角啊。不傻的都知道要预处理一张组合数表，但是你以为这样就可以了吗？？？显然，不可能的。那询问的时候复杂度就成了$\large{O(t*n)}$，凉凉。那咋办，用二维前缀和啊。在处理杨辉三角的时候顺便$\large{\mod k}$，否则会爆掉$\large{longlong}$我不知道，我猜的。二维前缀和应该都会，不会的自行百度。

下面的话等你看完代码再来看

这里说一下代码中有一句是这样的

mat[i][i+1] = mat[i][i];

　　

很多人都想问为什么，我来和大家说说。我们询问的时候边界到了极限情况下会贴着杨辉三角的斜边下来。那么预处理的时候就需要处理边界情况，就要用到边界外面的一列，当然它是斜着的。

又因为杨慧三角只有一半。所以边界后面的一列就没有东西了，所以直接继承过去就好了

　　

代码

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int n, m, k, T, x, f, c[2005][2005], mat[2005][2005];

char ch;

inline int read() {

	x = 0, f = 1;

	ch = getchar();

	while (ch < '0' || ch > '9') {

		if(ch == '-') f = -1;

		ch = getchar();

	}

	while (ch <= '9' && ch >= '0') {

		x = x*10 + ch-'0';

		ch = getchar();

	}

	return x * f;

}

int main() {

	T = read(); k = read();

	c[1][0] = 1, c[1][1] = 1, c[2][0] = 1;

	for(register int i=2; i<=2000; i++) {

		c[i][0] = 1;

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

			c[i][j] = (c[i-1][j] % k + c[i-1][j-1] % k) % k;

	}

	for(register int i=2; i<=2000; i++) {

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

			mat[i][j] = mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];

			if(c[i][j] == 0) mat[i][j] ++;

		}

		mat[i][i+1] = mat[i][i];

	}

	while (T--) {

		n = read(); m = read();

		if(m > n) m = n;

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

	}

	return 0;

}