记录编号	357390	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]组合数问题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.821 s
提交时间	2016-12-11 06:35:25	内存使用	31.11 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2010;
int q,n,m,p,c[maxn][maxn]={{0}},a[maxn][maxn]={{0}};
int main(){
#define MINE
#ifdef MINE
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
#endif
	scanf("%d%d",&q,&p);
	c[0][0]=1;
	for(int i=1;i<=2000;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
			if(!c[i][j])a[i][j]=1;
		}
	}
	for(int i=1;i<=2000;i++){
		a[i][0]+=a[i-1][0];
		a[0][i]+=a[0][i-1];
		for(int j=1;j<=2000;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	}
	while(q--){
		scanf("%d%d",&n,&m);
		printf("%d\n",a[n][m]);
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}