组合数

一个类似杨辉三角的东西，暴力写杨辉三角大概可以得到90分。但是这道题的优化却十分的诡异。

#define 巧妙 诡异

巧妙取模 pts:95分.
维护前缀和+递推打表 pts:100分.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int t,k;
int f[2005][2005];
int c[2005][2005];
int main() {
	t=read(),k=read();
	for(int i=0; i<=2000; i++) f[i][0]=f[i][i]=1;
	for(int i=1; i<=2000; i++) {
		for(int j=1; j<=i; j++) {
			f[i][j]=((f[i-1][j-1]%k)+(f[i-1][j]%k))%k;
		}
	}
	for(int i=1; i<=2000; i++) {
		for(int j=1; j<=2000; j++) {
			c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
			if(!f[i][j]&&i>=j)c[i][j]++;
		}
	}
	for(int i=1; i<=t; i++) {
		int n,m;
		n=read(),m=read();
		printf("%d
",c[n][m]);
	}
}