记录编号	436890	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]组合数问题	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.218 s
提交时间	2017-08-12 22:21:01	内存使用	31.25 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2010;
const int maxt=1e4+10;
int d[maxn][maxn];
int sum[maxn][maxn];
int wen[maxt][3],tot;
int t,n,m,k;
int maxx,maxy;
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){
	for(int i=x;i<=maxx;i+=lowbit(i)){
		for(int j=y;j<=maxy;j+=lowbit(j)){
			sum[i][j]++;
		}
	}
}
inline int find(int x,int y){
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i)){
		for(int j=y;j>0;j-=lowbit(j)){
			ans+=sum[i][j];
		}
	}
	return ans;
}
int main(){
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout); 
	scanf("%d%d",&t,&k);
	d[0][0]=d[1][0]=d[1][1]=1;
	maxx=maxy=-0x7fffffff; 
	while(t--){
		scanf("%d%d",&n,&m);
		maxx=max(maxx,n);maxy=max(maxy,m);
		wen[++tot][1]=n,wen[tot][2]=m;
	}
	for(int i=2;i<=maxx;i++){
		for(int j=0;j<=maxy;j++){
			if(j-1>=0&&j<=i){ 
				d[i][j]=(d[i-1][j]+d[i-1][j-1])%k;
				if(d[i][j]==0)add(i,j);
			}
			if(j==0){
				d[i][j]=(d[i-1][j])%k;
				if(d[i][j]==0)add(i,j);
			} 
		}
	}
	for(int i=1;i<=tot;i++){
		printf("%d\n",find(wen[i][1],wen[i][2]));
	} 
	return 0;
}